Four-coloring P₆-free graphs

DOI10.1137/1.9781611975482.76MaRDI QIDQ5236260zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Sophie Spirkl, Mingxian Zhong

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

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

Recommendations

• 4-colorability of P₆-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Complexity of coloring graphs without paths and cycles
• 4-coloring \(H\)-free graphs when \(H\) is small
• Obstructions for three-coloring graphs without induced paths on six vertices

Cited in

(39)

• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Colouring square-free graphs without long induced paths
• A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
• scientific article; zbMATH DE number 7525468 (Why is no real title available?)
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• Colouring H-free graphs of bounded diameter.
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• \((2P_2,K_4)\)-free graphs are 4-colorable
• An intractability result for the vertex 3-colourability problem
• Colouring \((P_r + P_s)\)-free graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• Colouring graphs with no induced six-vertex path or diamond
• Colouring graphs with no induced six-vertex path or diamond
• Obstructions for three-coloring graphs without induced paths on six vertices
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• Characterization of \(P_{6}\)-free graphs
• A new characterization of \(P_{6}\)-free graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• 4-colorability of P₆-free graphs
• Near optimal colourability on hereditary graph families
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• Connected greedy coloring of H-free graphs
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Coloring \((4K_1,C_4,C_6)\)-free graphs
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
• Restricted coloring problems on graphs with few \(P'_4s\)

This page was built for publication: Four-coloring \(P_6\)-free graphs

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