Light Graphs In Planar Graphs Of Large Girth

• Autorzy: Peter Hudák , Mária Maceková , Tomáš Madaras , Pavol Široczki
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graph; girth; light graph

Kategorie tematyczne

• 05C10: Planar graphs; geometric and topological aspects of graph theory

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 227-238

Daty

wydano

2016-02-01

otrzymano

2015-02-06

poprawiono

2015-06-08

zaakceptowano

2015-06-08

online

2016-01-19

Twórcy

autor

Peter Hudák

• Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

autor

Mária Maceková

• Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

autor

Tomáš Madaras

• Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

autor

Pavol Široczki

• Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia

Bibliografia

• [1] K. Appel and W. Haken, Every Planar Map is Four-Colorable (Providence, RI, American Mathematical Society, 1989). doi:10.1090/conm/098[Crossref]
• [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.
• [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
• [6] S. Jendrol’, M. Maceková, M. Montassier and R. Soták, Unavoidable 3-paths in planar graphs of given girth, manuscript.
• [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]
• [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]
• [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.
• [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]
• [12] D.B. West, Introduction to Graph Theory (Prentice Hall, 2001).

Identyfikatory

DOI

10.7151/dmgt.1847