Skip to main content
Springer Nature Link
Log in

On Edge-maps whose Inverse Preserves Flows or Tensions

  • Chapter
Graph Theory in Paris

Part of the book series: Trends in Mathematics ((TM))

Abstract

A cycle of a graph G is a set C ⊑ E(G) so that every vertex of the graph (V (G), C) has even degree. If G,H are graphs, we define a map φ: E(G) → E(H) to be cycle-continuous if the pre-image of every cycle of H is a cycle of G. A fascinating conjecture of Jaeger asserts that every bridgeless graph has a cycle-continuous mapping to the Petersen graph. Jaeger showed that if this conjecture is true, then so is the 5-cycle-double-cover conjecture and the Fulkerson conjecture.

Cycle continuous maps give rise to a natural quasi-order ≻ on the class of finite graphs. Namely, G ≻ H if there exists a cycle-continuous mapping from G to H. The goal of this paper is to establish some basic structural properties of this (and other related) quasi-orders. For instance, we show that ≻ has antichains of arbitrarily large finite size. It appears to be an interesting question to determine if ≻ has an infinite antichain.

Supported by Project LN00A056 and 1M0021620808 of the Czech Ministery of Education.

Supported by Barrande 02887WD P.A.I. Franco-Tchèque.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from €39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
EUR 106.99
Price includes VAT (Germany)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. D.A. Holton, J. Sheehan, The Petersen Graph, Australian Mathematical Society Series, 7. Cambridge University Press, 1993

    Google Scholar 

  2. A.J. Bondy, Basic Graph Theory: Paths and Circuits. Handbook of Combinatorics, edited by R. Graham, M. Grötschel and L. Lovász. (1995), 3–110

    Google Scholar 

  3. U. Celmins, On cubic graphs that do not have an edge 3-coloring. Ph. D. Thesis. University of Waterloo (1984)

    Google Scholar 

  4. M. DeVos, J. Nešetřil, A. Raspaud, On flow and tension-continuous maps. KAMDIMATIA Series 2002-567.

    Google Scholar 

  5. D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra. Math. Prog. 1 (1971), 168–194.

    Article  MathSciNet  MATH  Google Scholar 

  6. L.A. Goddyn, M. Tarsi, C-Q. Zhang, On (k,d)-colorings and fractional nowhere zero flows, J. Graph Theory 28 (1998), 155–161.

    Article  MathSciNet  MATH  Google Scholar 

  7. P. Hell and J. Nešetřil, Graphs and Homomorphisms, Oxford University Press, 2004.

    Google Scholar 

  8. F. Jaeger, A survey of the cycle double cover conjecture. Cycles in Graphs, Ann. Discrete Mathematics 27, North-Holland, Amsterdam, 1985, pp. 1–12.

    Google Scholar 

  9. F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory, Ser. B 26, 205–216 (1979).

    Article  MathSciNet  MATH  Google Scholar 

  10. F. Jaeger, On graphic-minimal spaces, Ann. Discrete Math. 8, 123–126 (1980).

    Article  MathSciNet  MATH  Google Scholar 

  11. F. Jaeger, Nowhere zero-flow problems. Selected topics in Graph Theory 3 Academic Press, London 1988, 71–95.

    Google Scholar 

  12. F. Jaeger, On circular flows in graphs in Finite and Infinite Sets, volume 37 of Colloquia Mathematica Societatis Janos Bolyai, edited by A. Hajnal, L. Lovasz, and V.T. Sos. North-Holland (1981) 391–402.

    Google Scholar 

  13. N. Linial, R. Meshulam, M. Tarsi, Matroidal bijections between graphs J. Comb. Theory, Ser. B 45, No.1, 31–44 (1988).

    Article  MathSciNet  MATH  Google Scholar 

  14. L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hung. 18 (1967), 321–329.

    Article  MATH  Google Scholar 

  15. M. Mihail, P. Winkler, On the number of Eulerian orientations of a graph, Proc. of the 3rd ACM-SIAM Symp. on Discrete Algorithms (1992), pp. 138–145.

    Google Scholar 

  16. V. Müller, The edge reconstruction hypothesis is true for graphs with more than nlogn edges, J. Comb. Th. B, 22 (1977), 281–183.

    Article  Google Scholar 

  17. J. Nešetřil, Aspects of Structural Combinatorics, Taiwanese J. Math. 3,4 (1999), 381–424.

    MathSciNet  MATH  Google Scholar 

  18. J. Nešetřil, C. Tardif, Duality Theorems for Finite Structures (Characterizing Gaps and Good Characterizations), J. Comb. Th. B 80 (2000), 80–97.

    Article  MATH  Google Scholar 

  19. J. Nešetřil, X. Zhu, Paths homomorphisms, Proc. Cambridge Phi. Soc. 120 (1996), 207–220.)

    Article  MATH  Google Scholar 

  20. R. Rizzi, On packing T-joins, manuscript.

    Google Scholar 

  21. G. C. Rota, On the foundations of combinatorial theory. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 1964 340–368 (1964).

    Article  MathSciNet  MATH  Google Scholar 

  22. M. Preissmann, Sur les colorations des arêtes des graphes cubiques. Thèse de Doctorat de 3ème cycle. Grenoble (1981)

    Google Scholar 

  23. P. Seymour, Nowhere-zero 6-flows, J. Comb. Theory, Ser. B 30, 130–135 (1981).

    Article  MathSciNet  MATH  Google Scholar 

  24. P.D. Seymour, Nowhere-zero flows. Handbook of Combinatorics, edited by R. Graham, M. Grötschel and L. Lovász. (1995), 289–299

    Google Scholar 

  25. W.T. Tutte, A contribution to the theory of chromatic polynomials, Can. J. Math. 6, 80–91 (1954).

    MathSciNet  MATH  Google Scholar 

  26. W.T. Tutte, A class of A belian groups, Can. J. Math. 8, 13–28 (1956).

    MathSciNet  MATH  Google Scholar 

  27. D. Welsh, Complexity: knots, colourings and counting. London Mathematical Society Lecture Note Series, 186. Cambridge University Press, Cambridge, 1993.

    MATH  Google Scholar 

  28. C.Q. Zhang, Circular flows of nearly Eulerian graphs and vertex-splitting. J. Graph Theory 40 (2002), no. 3, 147–161.

    Article  MathSciNet  MATH  Google Scholar 

  29. C.Q. Zhang, Integer flows and cycle covers of graphs, Pure and Applied Mathematics, Marcel Dekker. 205. New York, NY: Marcel Dekker.

    Google Scholar 

  30. X. Zhu, Circular Chromatic Number of Planar Graphs with large odd Girth, Electronic J. Comb. 2001, #25.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Applied Math Department, Princeton University, Princeton, NJ, 08544, USA

    Matt DeVos

  2. Department of Applied Mathematics (KAM) Institut for Theoretical Computer Sciences (ITI), Charles University, 11800, Prague, Czech Republic

    Jaroslav Nešetřil

  3. LaBRI, Université Bordeaux I, F-33405, Talence Cedex, France

    André Raspaud

Authors
  1. Matt DeVos
    View author publications

    Search author on:PubMed Google Scholar

  2. Jaroslav Nešetřil
    View author publications

    Search author on:PubMed Google Scholar

  3. André Raspaud
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 boulevard du 11 novembre 1918, 69622, Villeurbanne cedex, France

    Adrian Bondy

  2. Equipe Combinatoire et Optimisation Case 189, Université Pierre et Marie Curie, Paris 6, 75252, Paris Cedex 05, France

    Jean Fonlupt , Jean-Claude Fournier  & Jorge L. Ramírez Alfonsín ,  & 

  3. Laboratoire d’Informatique Fondamentale d’Orléans, Bâtiment IIIA, Rue Léonard de Vinci, B.P. 6759, 45067, Orléans Cedex 2, France

    Jean-Luc Fouquet

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Birkhäuser Verlag Basel/Switzerland

About this chapter

Cite this chapter

DeVos, M., Nešetřil, J., Raspaud, A. (2006). On Edge-maps whose Inverse Preserves Flows or Tensions. In: Bondy, A., Fonlupt, J., Fouquet, JL., Fournier, JC., Ramírez Alfonsín, J.L. (eds) Graph Theory in Paris. Trends in Mathematics. Birkhäuser Basel. https://doi.org/10.1007/978-3-7643-7400-6_10

Download citation

Publish with us

Policies and ethics