Coloring square-free Berge graphs - Laboratoire d'excellence en Mathématiques et informatique fondamentale de Lyon Accéder directement au contenu
Article Dans Une Revue Journal of Combinatorial Theory, Series B Année : 2019

Coloring square-free Berge graphs

Résumé

We consider the class of Berge graphs that do not contain a chordless cycle of length 4. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class.
Fichier principal
Vignette du fichier
1509.09195.pdf (362.45 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01993462 , version 1 (02-01-2021)

Identifiants

Citer

Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vušković. Coloring square-free Berge graphs. Journal of Combinatorial Theory, Series B, 2019, 135, pp.96-128. ⟨10.1016/j.jctb.2018.07.010⟩. ⟨hal-01993462⟩
113 Consultations
48 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More