Extremal Values of the Chromatic Number for a Given Degree Sequence - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Graphs and Combinatorics Année : 2017

Extremal Values of the Chromatic Number for a Given Degree Sequence

Résumé

For a degree sequence d : d 1 ≥ · · · ≥ d n , we consider the smallest chromatic number χ min (d) and the largest chromatic number χ max (d) among all graphs with degree sequence d. We show that if d n ≥ 1, then χ min (d) ≤ max 3, d 1 − n+1 4d 1 + 4 , and, if n + 1 4 − 1 2 > d 1 ≥ d n ≥ 1, then χ max (d) = max i∈[n] min {i, d i + 1}. For a given degree sequence d with bounded entries, we show that χ min (d), χ max (d), and also the smallest independence number α min (d) among all graphs with degree sequence d, can be determined in polynomial time.
Fichier principal
Vignette du fichier
1609.08919.pdf (154.13 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01997424 , version 1 (20-12-2019)

Identifiants

Citer

Stéphane Bessy, Dieter Rautenbach. Extremal Values of the Chromatic Number for a Given Degree Sequence. Graphs and Combinatorics, 2017, 33 (4), pp.789-799. ⟨10.1007/s00373-017-1814-3⟩. ⟨lirmm-01997424⟩
75 Consultations
90 Téléchargements

Altmetric

Partager

More