Like the well known
2+$p$-{\sc Sat} problem, the 2+$p$-{\sc Col}
problem smoothly interpolates between P and NP
by mixing together the polynomial 2-coloring problem
and the NP-complete 3-coloring problem.
As with 2+$p$-{\sc Sat}, the polynomial subproblem
can dominate the problem's solubility and
the search complexity.
The 2+p-COL problem class has, however, at least
one very significant difference over
the 2+p-SAT problem class. 2-SAT and 3-SAT
(and thus 2+p-SAT) have sharp transitions in
satisfiability. On the other hand,
3-COL has a sharp transition in solubility
but 2-COL has a smooth transition.
In the 2+p-COL problem, we therefore observe
phase transition behavior in which there appear
to be both smooth
and sharp regions. We also show how this problem
class can help to understand algorithm behavior
by considering search trajectories
through the phase space.
