Résumé
The 4-coloring problem is NP-complete for P7 $$P_7$$ -free graphs whereas the 3-coloring problem can be solved in quasi-polynomial time on Pt $$P_t$$ -free graphs for any fixed t. We consider circular coloring to locate precisely the complexity gap between 3 and 4 colors: for every fixed integer m≥2 $$m\ge 2$$ , the 3+1/m $$3+1/m$$ -coloring problem is NP-complete on P30 $$P_{30}$$ -free graphs.