Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring

DOI10.1137/18m1234849arXiv1802.02283MaRDI QIDQ6154191

Sophie Spirkl, Mingxian Zhong, Maria Chudnovsky

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

algorithmpathinduced subgraphcoloring

Mathematics Subject Classification ID

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

Related Items (1)

Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs

Cites Work

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

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