Complexity of Coloring Graphs without Paths and Cycles

DOI10.1007/978-3-642-54423-1_47zbMath1405.68140arXiv1310.0340OpenAlexW1500269355MaRDI QIDQ5405071

Shenwei Huang, Pavol Hell

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.0340

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, Coloring graphs without short cycles and long induced paths, 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Obstructions for three-coloring graphs without induced paths on six vertices