Light Graphs In Planar Graphs Of Large Girth

Peter Hudák; Mária Maceková; Tomáš Madaras; Pavol Široczki

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 227-238
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Peter Hudák, et al. "Light Graphs In Planar Graphs Of Large Girth." Discussiones Mathematicae Graph Theory 36.1 (2016): 227-238. <http://eudml.org/doc/276966>.

@article{PeterHudák2016,
abstract = {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.},
author = {Peter Hudák, Mária Maceková, Tomáš Madaras, Pavol Široczki},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; girth; light graph},
language = {eng},
number = {1},
pages = {227-238},
title = {Light Graphs In Planar Graphs Of Large Girth},
url = {http://eudml.org/doc/276966},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Peter Hudák
AU - Mária Maceková
AU - Tomáš Madaras
AU - Pavol Široczki
TI - Light Graphs In Planar Graphs Of Large Girth
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 227
EP - 238
AB - 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.
LA - eng
KW - planar graph; girth; light graph
UR - http://eudml.org/doc/276966
ER -

References

top
  1. [1] K. Appel and W. Haken, Every Planar Map is Four-Colorable (Providence, RI, American Mathematical Society, 1989). doi:10.1090/conm/098[Crossref] Zbl0681.05027
  2. [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. Zbl0694.05027
  3. [3] D.W. Cranston and D.B. West, A guide to the discharging method, arXiv:1306.4434 [math.CO] (2013). 
  4. [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. [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 Zbl1311.05042
  6. [6] S. Jendrol’, M. Maceková, M. Montassier and R. Soták, Unavoidable 3-paths in planar graphs of given girth, manuscript. Zbl1327.05081
  7. [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] Zbl0988.05031
  8. [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] Zbl1259.05045
  9. [9] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.Čas. SAV (Math. Slovaca) 5 (1955) 101–113. 
  10. [10] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43. Zbl0024.28701
  11. [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] Zbl0883.05056
  12. [12] D.B. West, Introduction to Graph Theory (Prentice Hall, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.