Skip to Main content Skip to Navigation
Journal articles

Extremal Values of the Chromatic Number for a Given Degree Sequence

Stéphane Bessy 1 Dieter Rautenbach 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01997424
Contributor : Stéphane Bessy <>
Submitted on : Friday, December 20, 2019 - 12:31:49 PM
Last modification on : Friday, December 20, 2019 - 12:49:07 PM
Document(s) archivé(s) le : Saturday, March 21, 2020 - 6:07:41 PM

File

1609.08919.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

114

Files downloads

87