Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
From MaRDI portal
Publication:2931404
DOI10.1145/1132516.1132576zbMath1301.05334MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Unnamed Item, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Some recent progress and applications in graph minor theory, A relaxed Hadwiger's conjecture for list colorings, Linear connectivity forces large complete bipartite minors, Note on coloring graphs without odd-\(K_k\)-minors, List-coloring graphs without \(K_{4,k}\)-minors, On the excluded minor structure theorem for graphs of large tree-width