# 3-Paths in Graphs with Bounded Average Degree

Stanislav Jendrol′; Mária Maceková; Mickaël Montassier; Roman Soták

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 339-353
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topStanislav 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 -

## References

top- [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[Crossref] Zbl1042.05078
- [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[Crossref][WoS] Zbl1280.05026
- [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[Crossref] Zbl0932.05033
- [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[Crossref] Zbl0893.52007
- [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[WoS][Crossref] Zbl1302.05040
- [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[Crossref] Zbl1311.05042

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.