Cycle Double Covers of Infinite Planar Graphs
Mohammad Javaheri
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 523-544 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:285515 
@article{bwmeta1.element.doi-10_7151_dmgt_1879,
     author = {Mohammad Javaheri},
     title = {Cycle Double Covers of Infinite Planar Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {523-544},
     zbl = {1339.05315},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1879}
}

Mohammad Javaheri. Cycle Double Covers of Infinite Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 523-544. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1879/

[1] J.C. Bermond, B. Jackson and F. Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B 35 (1993) 297-308. doi:10.1016/0095-8956(83)90056-4[Crossref]

[2] G. Brinkmann, J. Goedgebeur, J. Hägglund and K. Markström, Generation and properties of snarks, J. Combin. Theory Ser. B 103 (2013) 468-488. doi:10.1016/j.jctb.2013.05.001[WoS][Crossref] | Zbl 1301.05119

[3] H. Bruhn and M. Stein, MacLane’s planarity criterion for locally finite graphs, J. Combin. Theory Ser. B 96 (2006) 225-239. doi:10.1016/j.jctb.2005.07.005[Crossref]

[4] M. Chan, A survey of the cycle double cover conjecture, (2009).

[5] N.G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Nederl. Akad. Wetensch. Porc. Ser. A 54 (1951) 369-373. | Zbl 0044.38203

[6] R. Diestel, The cycle space of an infinite graph, Combin. Probab. Comput. 14 (2005) 59-79. doi:10.1017/S0963548304006686[Crossref] | Zbl 1067.05037

[7] R. Diestel and D. Kühl, On infinite cycles I, Combinatorica 24 (2004) 69-89. doi:10.1007/s00493-004-0005-z[Crossref] | Zbl 1063.05076

[8] R. Diestel and D. Kühl, On infinite cycles II, Combinatorica 24 (2004) 91-116. doi:10.1007/s00493-004-0006-y[Crossref] | Zbl 1063.05076

[9] G. Fan, Covering graphs by cycles, SIAM J. Discrete Math. 5 (1992) 491-496. doi:10.1137/0405039[Crossref] | Zbl 0777.05087

[10] I. Fary, On straight line representations of planar graphs, Acta Sci. Math. (Szeged) 11 (1984) 229-233.

[11] H. Fleischner, Proof of the strong 2-cover conjecture for planar graphs, J. Combin. Theory Ser. B 40 (1986) 229-230. doi:10.1016/0095-8956(86)90080-8[Crossref] | Zbl 0587.05041

[12] H. Fleischner and R. Häggkvist, Circuit double covers in special types of cubic graphs, Discrete Math. 309 (2009) 5724-5728. doi:10.1016/j.disc.2008.05.018[WoS][Crossref] | Zbl 1218.05129

[13] L. Goddyn, A girth requirement for the double cycle cover conjecture, Ann. Discrete Math. 27 (1985) 13-26. doi:10.1016/s0304-0208(08)72994-3[Crossref] | Zbl 0585.05013

[14] J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Discrete Math. 312 (2012) 2540-2544. doi:10.1016/j.disc.2011.08.024[WoS][Crossref] | Zbl 1246.05086

[15] A. Hoffmann-Ostenhof, A note on 5-cycle double covers, Graphs Combin. 29 (2013) 977-979. doi:10.1007/s00373-012-1169-8[Crossref] | Zbl 1268.05158

[16] A. Huck, Reducible configurations for the cycle double cover conjecture, Discrete Appl. Math. 99 (2000) 71-90. doi:10.1016/S0166-218X(99)00126-2[Crossref] | Zbl 0966.05045

[17] R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221-239. doi:10.2307/2319844[Crossref] | Zbl 0311.05109

[18] F. Jaeger, A survey of the cycle double cover conjecture, Ann. Discrete Math. 27 (1985) 1-12. doi:10.1016/s0304-0208(08)72993-1[Crossref]

[19] F. Jaeger, On circular flows in graphs, Proc. Colloq. Math. Janos Bolyai (1982) 391-402.

[20] S. MacLane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937) 22-32. | Zbl 0015.37501

[21] P.D. Seymour, Disjoint paths in graphs, Discrete Math. 29 (1980) 293-309. doi:10.1016/0012-365X(80)90158-2[Crossref]

[22] P.D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130-135. doi:10.1016/0095-8956(81)90058-7[Crossref] | Zbl 0474.05028

[23] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Aust. Math. Soc. 8 (1973) 367-387. doi:10.1017/S0004972700042660[Crossref] | Zbl 0249.05111

[24] P.G. Tait, Remarks on the colourings of maps, Proc. Roy. Soc. Edinburgh Sect. A 10 (1880) 729.[Crossref]

[25] C. Thomassen, Planarity and duality of finite and infinite graphs, J. Combin. Theory Ser. B 29 (1980) 244-271. doi:10.1016/0095-8956(80)90083-0[Crossref]

[26] C. Thomassen, Straight line representation of infinite planar graphs, J. Lond. Math. Soc. (2) 16 (1977) 411-423. doi:10.1112/jlms/s2-16.3.411[Crossref] | Zbl 0373.05032

[27] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91. doi:10.4153/CJM-1954-010-9[Crossref]

[28] K. Wagner, Fastplättbare Graphen, J. Combin. Theory 3 (1967) 326-365. doi:10.1016/S0021-9800(67)80103-0[Crossref]

[29] R. Xu, Strong 5-cycle double covers of graphs, Graphs Combin. 30 (2014) 495-499. doi:10.1007/s00373-012-1266-8[Crossref] | Zbl 1298.05180

[30] D. Ye, Perfect Matching and Circuit Cover of Graphs (Ph.D. Dissertation, West Virginia University, 2012).