Obstructions for three-coloring graphs with one forbidden induced subgraph

DOI10.1137/1.9781611974331.ch123zbMath1410.05063OpenAlexW4244448516MaRDI QIDQ4575707

Oliver Schaudt, Jan Goedgebeur, Maria Chudnovsky, 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

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

Related Items

Dynamic \(F\)-free coloring of graphs, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, 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, Critical (\(P_5\), bull)-free graphs, Computational aspects of greedy partitioning of graphs, Critical vertices and edges in \(H\)-free graphs, Critical \((P_6, \mathrm{banner})\)-free graphs, 3-Colorable Subclasses of $P_8$-Free Graphs, Obstructions for three-coloring graphs without induced paths on six vertices, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, CriticalPfreeGraphs