Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring

DOI10.1137/18m1234837arXiv1802.02282MaRDI QIDQ6122199

Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

Publication date: 28 February 2024

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

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

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
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary

This page was built for publication: Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring