Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs

DOI10.1145/1132516.1132576zbMath1301.05334OpenAlexW2129907634MaRDI QIDQ2931404

Bojan Mohar, Ken-ichi Kawarabayashi

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132576

zbMATH Keywords

graph coloringgraph minorHadwiger conjecturelist coloringodd minor

Mathematics Subject Classification ID

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

Related Items

Some recent progress and applications in graph minor theory, A relaxed Hadwiger's conjecture for list colorings, On the excluded minor structure theorem for graphs of large tree-width, Linear connectivity forces large complete bipartite minors, Note on coloring graphs without odd-\(K_k\)-minors, List-coloring graphs without \(K_{4,k}\)-minors, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Unnamed Item