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.
@article{bwmeta1.element.doi-10_7151_dmgt_1859,
author = {Stanislav Jendrol' and Maria Macekova and Mickael Montassier and Roman Sotak},
title = {3-Paths in Graphs with Bounded Average Degree},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {339-353},
zbl = {1338.05054},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1859}
}
Stanislav Jendrol′; Mária Maceková; Mickaël Montassier; Roman Soták. 3-Paths in Graphs with Bounded Average Degree. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 339-353. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1859/