Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs

Abstract

The $k$-Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs. We say that a graph is $(H_1,H_2,\dots )$-free if it does not contain any of $H_1,H_2,\dots$ as induced subgraphs. The complexity landscape of the problem remains unclear even when restricting to the case $k=4$ and classes defined by a few forbidden induced subgraphs. While the case of only one forbidden induced subgraph has been completely resolved lately, the complexity when considering two forbidden induced subgraphs still has a couple of unknown cases. In particular, $4$-Coloring on $(P_6,C_3)$-free graphs is polynomial while it is NP-hard on $(P_{22},C_3)$-free graphs. We provide a reduction showing NP-completeness of $4$-Coloring on $(P_t,C_3)$-free graphs for $19\le t\le 21$, thus constricting the gap of cases whose complexity remains unknown. Our proof includes a computer search ensuring that the graph family obtained through the reduction is indeed $P_{19}$-free.

15 pages, 7 figures