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

Abstract

top
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.

How to cite

top

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 -

References

top
  1. [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. [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. [3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  4. [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. [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. [6] D.W. Cranston and D.B.West, A guide to the discharging method, arXiv: 1306.4434 [math.CO] 19 Jun 2013. 
  7. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.