Abstract
For a degree sequence \(d:d_1\ge \cdots \ge d_n\), we consider the smallest chromatic number \(\chi _{\min }(d)\) and the largest chromatic number \(\chi _{\max }(d)\) among all graphs with degree sequence d. We show that if \(d_n\ge 1\), then \(\chi _{\min }(d)\le \max \left\{ 3,d_1-\frac{n+1}{4d_1}+4\right\} \), and, if \(\sqrt{n+\frac{1}{4}}-\frac{1}{2}>d_1\ge d_n\ge 1\), then \(\chi _{\max }(d)=\max \nolimits _{i\in [n]}\min \left\{ i,d_i+1\right\} \). For a given degree sequence d with bounded entries, we show that \(\chi _{\min }(d), \chi _{\max }(d)\), and also the smallest independence number \(\alpha _{\min }(d)\) among all graphs with degree sequence d, can be determined in polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bauer, D., Hakimi, S.L., Kahl, N., Schmeichel, E., Bauer, D., Hakimi, S.L., Kahl, N., Schmeichel, E.: Best monotone degree bounds for various graph parameters. Congr. Numer. 192, 75–84 (2008)
Caro, Y.: New results on the independence number, Technical Report, Tel-Aviv University (1979)
Dvořák, Z., Mohar, B.: Chromatic number and complete graph substructures for degree sequences. Combinatorica 33, 513–529 (2013)
Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices (Hungarian). Mat. Lapok 11, 264–274 (1960)
Gale, D.: A theorem on flows in networks. Pac. J. Math. 7, 1073–1082 (1957)
Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10, 496–506 (1962)
Harant, J., Rautenbach, D.: Independence in connected graphs. Discrete Appl. Math. 159, 79–86 (2011)
Harant, J., Schiermeyer, I.: On the independence number of a graph in terms of order and size. Discrete Math. 232, 131–138 (2001)
Havel, V.: A remark on the existence of finite graphs. Časopis Pro Pěstování Mat. 80, 477–480 (1955)
Kleitman, D.J., Wang, D.L.: Algorithms for constructing graphs and digraphs with given valences and factors. Discrete Math. 6, 79–88 (1973)
Punnim, N.: Degree sequences and chromatic numbers of graphs. Graphs Comb. 18, 597–603 (2002)
Rao, R.A.: The clique number of a graph with a given degree sequence. In: Proceedings of the Symposium on Graph Theory (Indian Statistical Institute, Calcutta, 1976). ISI Lecture Notes Series, vol. 4, pp. 251–267. Macmillan of India, New Delhi (1979)
Rao, A.R.: An Erdős–Gallai type result on the clique number of a realization of a degree sequence (unpublished)
Robertson, N., Song, Z.-X.: Hadwiger number and chromatic number for near regular degree sequences. J. Graph Theory 64, 175–183 (2010)
Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Can. J. Math. 9, 371–377 (1957)
Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10, 85–86 (1967)
Wei, V.K.: A lower bound on the stability number of a simple graph, Technical memorandum, TM 81-11217-9, Bell laboratories (1981)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bessy, S., Rautenbach, D. Extremal Values of the Chromatic Number for a Given Degree Sequence. Graphs and Combinatorics 33, 789–799 (2017). https://doi.org/10.1007/s00373-017-1814-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1814-3