Light Graphs In Planar Graphs Of Large Girth
Peter Hudák ; Mária Maceková ; Tomáš Madaras ; Pavol Široczki
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 227-238 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3 and C10.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:276966 
@article{bwmeta1.element.doi-10_7151_dmgt_1847,
     author = {Peter Hud\'ak and M\'aria Macekov\'a and Tom\'a\v s Madaras and Pavol \v Siroczki},
     title = {Light Graphs In Planar Graphs Of Large Girth},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {227-238},
     zbl = {1329.05083},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1847}
}

Peter Hudák; Mária Maceková; Tomáš Madaras; Pavol Široczki. Light Graphs In Planar Graphs Of Large Girth. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 227-238. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1847/

[1] K. Appel and W. Haken, Every Planar Map is Four-Colorable (Providence, RI, American Mathematical Society, 1989). doi:10.1090/conm/098[Crossref] | Zbl 0681.05027

[2] O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki 46(5) (1989) 9–12. | Zbl 0694.05027

[3] D.W. Cranston and D.B. West, A guide to the discharging method, arXiv:1306.4434 [math.CO] (2013).

[4] S. Jendrol’ and M. Maceková, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015) 149–158. doi:10.1016/j.disc.2014.09.014[Crossref][WoS]

[5] S. Jendrol’, M. Maceková and R. Soták, Note on 3-paths in plane graphs of girth 4, Discrete Math. 338 (2015) 1643–1648. doi:/10.1016/j.disc.2015.04.011 | Zbl 1311.05042

[6] S. Jendrol’, M. Maceková, M. Montassier and R. Soták, Unavoidable 3-paths in planar graphs of given girth, manuscript. | Zbl 1327.05081

[7] S. Jendrol’ and P.J. Owens, On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs Combin. 17 (2001) 659–680. doi:10.1007/s003730170007[Crossref] | Zbl 0988.05031

[8] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane - A survey, Discrete Math. 313 (2013) 406–421. doi:10.1016/j.disc.2012.11.007[Crossref][WoS] | Zbl 1259.05045

[9] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.Čas. SAV (Math. Slovaca) 5 (1955) 101–113.

[10] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43. | Zbl 0024.28701

[11] N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2–44. doi:10.1006/jctb.1997.1750[Crossref] | Zbl 0883.05056

[12] D.B. West, Introduction to Graph Theory (Prentice Hall, 2001).