2016/09/28 by Bessy, Stéphane, Rautenbach, Dieter
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.08919
For a degree sequence d:d1≥ ⋯ ≥ dn, 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 dn≥ 1, then χmin(d)≤ max\ 3,d1-(n+1)/(4d1)+4\, and, if √(n+(1)/(4))-(1)/(2)>d1≥ dn≥ 1, then χmax(d)=maxi∈ [n]min\ i,di+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.