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

BONOMO-BRABERMAN, FLAVIA; CHUDNOVSKY, MARIA; GOEDGEBEUR, JAN; MACELI, PETER; SCHAUDT, OLIVER; STEIN, MAYA; ZHONG, MINGXIAN

THEORETICAL COMPUTER SCIENCE

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2021 vol. 850 p. 98 - 115

0304-3975

We present an algorithm to color a graph $G$ with no triangle andno induced $7$-vertex path (i.e., a ${P_7,C_3}$-free graph), whereevery vertex is assigned a list of possible colors which is asubset of ${1,2,3}$. While this is a special case of the problemsolved in [Combinatorica 38(4):779--801, 2018], that does notrequire the absence of triangles, the algorithm here is bothfaster and conceptually simpler. The complexity of the algorithmis $O(|V(G)|^5(|V(G)|+|E(G)|))$, and if $G$ is bipartite, itimproves to $O(|V(G)|^2(|V(G)|+|E(G)|))$.Moreover, we prove thatthere are finitely many minimal obstructions to list 3-coloring${P_t,C_3}$-free graphs if and only if $t leq 7$. This implies the existence ofa polynomial time certifying algorithm for list 3-coloring in${P_7,C_3}$-free graphs.We furthermore determine other cases of $t, ell$, and $k$ such that the family of minimal obstructions to list $k$-coloring in ${P_t,C_{ell}}$-free graphs is finite.