Obstructions for three-coloring graphs with one forbidden induced subgraph

DOI10.1137/1.9781611974331.CH123MaRDI QIDQ4575707zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Publication date 16 July 2018

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

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

Mathematics Subject Classification ID

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

Recommendations

• Obstructions for three-coloring graphs without induced paths on six vertices
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Four-coloring \(P_6\)-free graphs
• Complexity of coloring graphs without paths and cycles
• List 3-coloring graphs with no induced \(P_6 + rP_3\)

Cited in

(20)

• Three forbidden subgraphs for line graphs
• Dynamic \(F\)-free coloring of graphs
• Computational aspects of greedy partitioning of graphs
• Critical vertices and edges in \(H\)-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• Colouring diamond-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• 3-colourability and forbidden subgraphs
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• CriticalPfreeGraphs
• 3-colorable subclasses of \(P_8\)-free graphs
• Obstructions for three-coloring and list three-coloring H-free graphs
• Critical (\(P_5\), bull)-free graphs
• A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
• Vertex-critical graphs in co-gem-free graphs
• A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems

This page was built for publication: Obstructions for three-coloring graphs with one forbidden induced subgraph

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