Bounding 𝝌 by 𝚫 and 𝝎
摘要
Brooks’ theorem may be stated as an upper bound on the chromatic number 𝜒 of a graph as a function of its maximum degree Δ and its clique number𝜔, so the question of a best possible such bound arises quite naturally. An answer to this question might be too difficult, but there are some interesting suggestions which we will address in this chapter.