3-Paths in Graphs with Bounded Average Degree

Stanislav Jendrol′, et al. "3-Paths in Graphs with Bounded Average Degree." Discussiones Mathematicae Graph Theory 36.2 (2016): 339-353. <http://eudml.org/doc/277118>.

@article{StanislavJendrol2016,
abstract = {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.},
author = {Stanislav Jendrol′, Mária Maceková, Mickaël Montassier, Roman Soták},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {average degree; structural property; 3-path; degree sequence},
language = {eng},
number = {2},
pages = {339-353},
title = {3-Paths in Graphs with Bounded Average Degree},
url = {http://eudml.org/doc/277118},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Stanislav Jendrol′
AU - Mária Maceková
AU - Mickaël Montassier
AU - Roman Soták
TI - 3-Paths in Graphs with Bounded Average Degree
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 339
EP - 353
AB - 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.
LA - eng
KW - average degree; structural property; 3-path; degree sequence
UR - http://eudml.org/doc/277118
ER -