Extremal Values of the Chromatic Number for a Given Degree Sequence - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Graphs and Combinatorics Year : 2017

Extremal Values of the Chromatic Number for a Given Degree Sequence

Abstract

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
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
72 View
87 Download

Altmetric

Share

More