Between 2- and 3-colorability

The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomial time. To make the complexity gap more precise, we study intermediate graph classes and respective problems. This note proposes a conjecture that separates difficult instances of the problem from polynomially solvable ones and proves the “polynomial” part of the conjecture.