Extremal Values of the Chromatic Number for a Given Degree Sequence

作者：Bessy Stephane; Rautenbach Dieter^*

来源：Graphs and Combinatorics, 2017, 33(4): 789-799.

DOI：10.1007/s00373-017-1814-3

• Degree sequence
• Chromatic number
• Independence number

For a degree sequence , we consider the smallest chromatic number and the largest chromatic number among all graphs with degree sequence d. We show that if , then , and, if , then . For a given degree sequence d with bounded entries, we show that , and also the smallest independence number among all graphs with degree sequence d, can be determined in polynomial time.

• 出版日期2017-7