4-coloring $P_6$-free graphs with no induced 5-cycles

arxiv: 1407.2487 · v1 · pith:WEZ53CLOnew · submitted 2014-07-09 · 💻 cs.DM · math.CO

4-coloring P₆-free graphs with no induced 5-cycles

Maria Chudnovsky , Peter Maceli , Juraj Stacho , Mingxian Zhong This is my paper

classification 💻 cs.DM math.CO

keywords inducedcoloringgraphscyclecyclesfreepathpolynomial

0 comments

read the original abstract

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_5$ and no induced 6-vertex path $P_6$.

This paper has not been read by Pith yet.