Geodesic
Light Graphs In Planar Graphs Of Large Girth
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 227-238.

Voir la notice de l'article provenant de la source Library of Science

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) deg_G (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 K_1,3 and C_10.
Keywords: planar graph, girth, light graph 
@article{DMGT_2016_36_1_a15,
     author = {Hud\'ak, Peter and Macekov\'a, M\'aria and Madaras, Tom\'a\v{s} and \v{S}iroczki, Pavol},
     title = {Light {Graphs} {In} {Planar} {Graphs} {Of} {Large} {Girth}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {227--238},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a15/}
}
TY  - JOUR
AU  - Hudák, Peter
AU  - Maceková, Mária
AU  - Madaras, Tomáš
AU  - Široczki, Pavol
TI  - Light Graphs In Planar Graphs Of Large Girth
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 227
EP  - 238
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a15/
LA  - en
ID  - DMGT_2016_36_1_a15
ER  - 
%0 Journal Article
%A Hudák, Peter
%A Maceková, Mária
%A Madaras, Tomáš
%A Široczki, Pavol
%T Light Graphs In Planar Graphs Of Large Girth
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 227-238
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a15/
%G en
%F DMGT_2016_36_1_a15
Hudák, Peter; Maceková, Mária; Madaras, Tomáš; Široczki, Pavol. Light Graphs In Planar Graphs Of Large Girth. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 227-238. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a15/

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

[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

[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

[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

[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

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