3-path in graphs with bounded average degree
Stanislav Jendrol′, Mária Maceková, Mickaël Montassier, Roman Soták · Discussiones Mathematicae Graph Theory · 2015
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 (2, 5, 3), (3, 2, 4), (3, 3, 3)