Better 3-coloring algorithms: excluding a triangle and a seven vertex path

Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur +4

We present an algorithm to color a graph $G$ with no triangle and no induced $7$-vertex path (i.e., a $\{P_7,C_3\}$-free graph), where every vertex is assigned a list of possible c…