Extremal Values of the Chromatic Number for a Given Degree Sequence - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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⟩
67 View
77 Download

Altmetric

Share

Gmail Facebook X LinkedIn More