Geodesic
3-Paths in Graphs with Bounded Average Degree
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 339-353.

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

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types Moreover, no parameter of this description can be improved.
Keywords: average degree, structural property, 3-path, degree sequence 
@article{DMGT_2016_36_2_a6,
     author = {Jendrol, Stanislav and Macekov\'a, M\'aria and Montassier, Micka\"el and Sot\'ak, Roman},
     title = {3-Paths in {Graphs} with {Bounded} {Average} {Degree}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {339--353},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/}
}
TY  - JOUR
AU  - Jendrol, Stanislav
AU  - Maceková, Mária
AU  - Montassier, Mickaël
AU  - Soták, Roman
TI  - 3-Paths in Graphs with Bounded Average Degree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 339
EP  - 353
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/
LA  - en
ID  - DMGT_2016_36_2_a6
ER  - 
%0 Journal Article
%A Jendrol, Stanislav
%A Maceková, Mária
%A Montassier, Mickaël
%A Soták, Roman
%T 3-Paths in Graphs with Bounded Average Degree
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 339-353
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/
%G en
%F DMGT_2016_36_2_a6
Jendrol, Stanislav; Maceková, Mária; Montassier, Mickaël; Soták, Roman. 3-Paths in Graphs with Bounded Average Degree. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 339-353. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a6/

[1] K. Ando, S. Iwasaki and A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum, in: Annual Meeting of Mathematical Society of Japan, (1993), in Japanese.

[2] P. Bose, M. Smid and D.R. Wood, Light edges in degree-constrained graphs, Discrete Math. 28 (2004) 35-41. doi:10.1016/j.disc.2003.12.003

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[4] O.V. Borodin, A.O. Ivanova, T.R. Jensen, A.V. Kostochka and M. Yancey, Describ- ing 3-paths in normal plane maps, Discrete Math. 313 (2013) 2702-2711. doi:10.1016/j.disc.2013.08.018

[5] O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud and E. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89. doi:10.1016/S0012-365X(98)00393-8

[6] D.W. Cranston and D.B.West, A guide to the discharging method, arXiv: 1306.4434 [math.CO] 19 Jun 2013.

[7] S. Jendrol′, A structural property of convex 3-polytopes, Geom. Dedicata 68 (1997) 91-99. doi:10.1023/A:1004993723280

[8] 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

[9] 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