Four-coloring P6-free graphs

DOI10.1137/1.9781611975482.76zbMath1431.05064OpenAlexW4238886873MaRDI QIDQ5236260

Maria Chudnovsky, Mingxian Zhong, Sophie Spirkl

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.76

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

Colouring graphs with no induced six-vertex path or diamond ⋮ The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ An intractability result for the vertex 3-colourability problem ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions ⋮ Unnamed Item ⋮ List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\) ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ Near optimal colourability on hereditary graph families ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Unnamed Item ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Colouring H-free graphs of bounded diameter. ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Connected greedy coloring of \(H\)-free graphs

This page was built for publication: Four-coloring P₆-free graphs