Approximately coloring graphs without long induced paths

Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl +2

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$. We…