
{\bf The 3-colorability problem on graphs with maximum degree 4}

{\it Martin Kochol; Vadim Lozin; Bert Randerath}


\bigskip

ABSTRACT:

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' Theorem in 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.


\bigskip

{\it AMS classification (1991): }
05C15

\bigskip

{\it Keywords: }
3-colorability, polynomial algorithms, NP-completeness, dichotomy

