Minimal graphs for which the chromatic number equals the maximal degree. (English) Zbl 0554.05025
In this paper graphs for which the chromatic number and the maximal degree are equal to the same number n are considered. It is proved that if such a graph has no \(K_ n\) as a subgraph, then \(| V(G)| \geq 2n-1\) and if G has exactly 2n-1 vertices, then \(n\leq 8\). With the help of a computer the authors showed that there are exactly 13 such graphs having \(2n-1\) vertices. One of these graphs is the smallest counterexample to the Hajos conjecture.
Reviewer: I.Tomescu