Four-Coloring P₆-Free Graphs. II. Finding an Excellent Precoloring

DOI10.1137/18M1234849MaRDI QIDQ6154191zbMATH OpenFDO

Authors Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Publication date 19 March 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02283

zbMATH Keywords

algorithminduced subgraphcoloringpath

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: This is the second paper in a series of two. The goal of the series is to give a polynomial time algorithm for the $4$-coloring problem and the $4$-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results this completes the classification of the complexity of the $4$-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time algorithm that starts with a $4$-precoloring of a graph with no induced six-vertex path, and outputs a polynomial-size collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem.

Recommendations

• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-coloring \(P_6\)-free graphs
• 4-colorability of P₆-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Three complexity results on coloring \(P _{k }\)-free graphs

Cites work

• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Coloring graphs with forbidden induced subgraphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• The complexity of colouring problems on dense graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Triangle-free graphs with no six-vertex induced path

Cited in

(2)

• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring

This page was built for publication: Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154191)