Improved Complexity Results on $k$-Coloring $P_t$-Free Graphs

Abstract

A graph is $H$-free if it does not contain an induced subgraph isomorphic to $H$. We denote by $P_k$ and $C_k$ the path and the cycle on $k$ vertices, respectively. In this paper, we prove that 4-COLORING is NP-complete for $P_7$-free graphs, and that 5-COLORING is NP-complete for $P_6$-free graphs. These two results improve all previous results on $k$-coloring $P_t$-free graphs, and almost complete the classification of complexity of $k$-COLORING $P_t$-free graphs for $k\ge 4$ and $t\ge 1$, leaving as the only missing case 4-COLORING $P_6$-free graphs. We expect that 4-COLORING is polynomial time solvable for $P_6$-free graphs; in support of this, we describe a polynomial time algorithm for 4-COLORING $P_6$-free graphs which are also $P$-free, where $P$ is the graph obtained from $C_4$ by adding a new vertex and making it adjacent to exactly one vertex on the $C_4$.

References in corpus (1)

• Complexity of Coloring Graphs without Paths and Cycles

Cited by in corpus (5)

• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Three-coloring graphs with no induced seven-vertex path II : using a triangle
• Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• 4-coloring $P_6$-free graphs with no induced 5-cycles