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

1 Introduction

• For fixed k ≥ 3, k-COLORING is NP-complete on graphs of girth at least any fixed g ≥ 3, while perfect graphs admit polynomial-time chromatic-number decisions.The introduction situates path-free coloring within broader complexity results for restricted graph classes.Source: §1 · pp. 1–2
• For P_t-free graphs, coloring is trivial when t ≤ 3; P4-free graphs are perfect, and k-COLORING is polynomial-time solvable on P5-free graphs for fixed k.P4-free graphs are also called cographs.Source: §1 · pp. 2–3
• 5-COLORING is NP-complete for P6-free graphs, and 4-COLORING is NP-complete for P7-free graphs.These results leave 4-COLORING on P6-free graphs as the only missing case in the stated classification for k ≥ 4 and t ≥ 1.Source: §1 · p. 3
• The paper develops a general reduction framework for both hardness results and gives a polynomial-time algorithm for 4-COLORING on (P6, P)-free graphs.Here, P is obtained from C4 by adding a vertex adjacent to exactly one C4 vertex.Source: §1 · p. 3

• 5-COLORING is NP-complete for P6-free graphs, and 4-COLORING is NP-complete for P7-free graphs.Source: §2 · p. 3
• A unified reduction framework builds a graph GH,I from a 3-SAT instance and a nice k-critical graph H.A nice k-critical graph has three specified independent vertices whose removal leaves the clique number unchanged at k − 1.Source: §2 · pp. 3–4
• The constructed graph GH,I is (k + 1)-colorable if and only if the 3-SAT instance I is satisfiable.Source: §2 · p. 4
• If H is Pt-free for t ≥ 6, the constructed graph GH,I is also Pt-free.Source: §2 · p. 5
• For the two hardness results, the framework uses a P6-free nice 4-critical graph H1 and the P7-free nice 3-critical graph C7.Applying Theorem 7 with these graphs yields the results for 5-COLORING on P6-free graphs and 4-COLORING on P7-free graphs.Source: §2 · p. 6

The Polynomial Result

• No P6-free nice 3-critical graph exists; the only possible P6-free odd-cycle 3-critical graph, C5, cannot contain three independent vertices.The authors also note that usual 3-COLORING techniques do not apply to 4-COLORING P6-free graphs.Source: §3 · p. 7
• 4-COLORING is polynomial-time solvable for (P6, P)-free graphs, where P is a C4 with a new vertex adjacent to exactly one C4 vertex.The proof uses polynomial-time list 3-coloring for P6-free graphs and a polynomial-time algorithm for lists of size at most two.Source: §3 · p. 7
• For a nonperfect 2-connected instance, the Strong Perfect Graph Theorem leaves an induced C5 or complement of C7 to analyze.The proof first removes the K5 case and handles perfect graphs by optimal coloring.Source: §3 · pp. 7–8
• In the complement-of-C7 case, P-freeness and connectivity force S0 to be empty, after which at most 4^7 colorings of C are tested and each reduces to 2-SAT.Here S0 contains vertices with no neighbors on C.Source: §3 · p. 8
• For an induced C5, P-freeness constrains neighborhoods: S5 must be independent, while the C-neighborhoods of vertices in S3 and S2 induce P3 and P2, respectively.These facts support the bounded precoloring step for C ∪ S4 ∪ S3; K5-freeness bounds each S3(vi) and S4(vi) to at most two vertices.Source: §3 · p. 8
• The C5 case fixes colors on C ∪ S4 ∪ S3, then tests whether the coloring extends using lists for the remaining vertices.There are at most 4^25 such colorings; after updating lists, S5 vertices have singleton lists and S2 vertices have lists of size at most two.Source: §3 · pp. 8–9
• For each component of S0, the proof uses its restricted adjacencies to S3 and S5 to decide list extension in polynomial time.Within a component, 0-vertices have identical S3-neighborhoods; the argument then applies Lemma 4 to the component.Source: §3 · p. 9
• A polynomial-cost branching procedure separates unprecolored S1 and S2 vertices, allowing their extensions to be checked independently by list-coloring lemmas.The proof derives adjacency constraints among S1 sets and between S1 and S2; in the remaining case, S2(v0) is a star and can be precolored in two ways.Source: §3 · pp. 9–10

4 Concluding Remarks

• 4-COLORING is NP-complete for P7-free graphs, and 5-COLORING is NP-complete for P6-free graphs, improving the cited earlier results.The paper says its reduction from 3-SAT gives a simpler construction and proof than previous papers.Source: §4 · p. 11
• The authors conjecture that 4-COLORING is polynomial-time solvable for P6-free graphs, the remaining case they identify in this classification.They note that the polynomial cases for H-free graphs with H a linear forest on at most five vertices are subclasses of P6-free graphs.Source: §4 · p. 11
• The conjecture holds for (P6, P)-free graphs, where P is a C4 with a new vertex adjacent to exactly one C4 vertex.The proof draws on ideas from Le et al. and suggests techniques the authors say may be useful.Source: §4 · p. 11
• The authors propose classifying k-COLORING on (Pt, Cl)-free graphs and ask whether forbidding short induced cycles makes coloring easier.They cite polynomial-time solvability for (P6, C4)-free graphs and NP-completeness for (P164, C3)-free graphs as contrasting results.Source: §4 · p. 11