The 3-Colorability Problem on Graphs with Maximum Degree Four
Martin Kochol, Vadim Lozin, Bert Randerath · SIAM Journal on Computing · 2003
The 3-colorability problem is known to be NP-complete in the class of graphs with maximum degree four. On the other hand, due to the celebrated theorem of Brooks, the problem has a polynomial-time solution for graphs with maximum degree three. To make the complexity gap more precise, we study a family of intermediate graph classes between these two extremes and classify all of them according to the computational complexity of the problem. In particular, we generalize Brooks's theorem in the case of 3-colorability to a larger class by showing that every connected graph in that class is 3-colorable, unless it is a complete graph on four vertices.