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

DOI10.1137/18M1234849arXiv1802.02283MaRDI QIDQ6154191FDOQ6154191

Authors: Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong 

Publication date: 19 March 2024

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

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.

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

Recommendations

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

zbMATH Keywords

algorithminduced subgraphcoloringpath

Mathematics Subject Classification ID

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

Cites Work

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

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)