Obstructions for three-coloring graphs with one forbidden induced subgraph
DOI10.1137/1.9781611974331.CH123zbMATH Open1410.05063OpenAlexW4244448516MaRDI QIDQ4575707FDOQ4575707
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cited In (17)
- Critical vertices and edges in \(H\)-free graphs
- 4-coloring \((P_6, \text{bull})\)-free graphs
- Certifying coloring algorithms for graphs without long induced paths
- On the chromatic number of (\(P_6\), diamond)-free graphs
- Obstructions for three-coloring and list three-coloring \(H\)-free graphs
- Dynamic \(F\)-free coloring of graphs
- Computational aspects of greedy partitioning of graphs
- Obstructions for three-coloring graphs without induced paths on six vertices
- Colouring diamond-free graphs
- 3-colourability and forbidden subgraphs
- Three forbidden subgraphs for line graphs
- CriticalPfreeGraphs
- Critical \((P_6, \mathrm{banner})\)-free graphs
- Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
- Critical (\(P_5\), bull)-free graphs
- 3-colorable subclasses of \(P_8\)-free graphs
- A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
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)
