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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.