3-path in graphs with bounded average degree

Stanislav Jendrol 1 Mária Maceková Mickaël Montassier 2 Roman Soták 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 to contains a path of one of the types (Equation presented) Moreover, no parameter of this description can be improved.
Type de document :
Article dans une revue
Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2016, 36 (2), pp.339-353. 〈10.7151/dmgt.1859〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01346642
Contributeur : Isabelle Gouat <>
Soumis le : mardi 19 juillet 2016 - 13:46:59
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Stanislav Jendrol, Mária Maceková, Mickaël Montassier, Roman Soták. 3-path in graphs with bounded average degree. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2016, 36 (2), pp.339-353. 〈10.7151/dmgt.1859〉. 〈lirmm-01346642〉

Partager

Métriques

Consultations de la notice

91