On the complexity of graph coloring with additional local conditions

DOI10.1016/j.ipl.2018.03.009zbMath1476.05190arXiv1712.03150OpenAlexW2772240417MaRDI QIDQ1708276

Yaroslav N. Shitov

Publication date: 5 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph coloringfixed-parameter tractability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• A note on local coloring of graphs
• Local coloring of Kneser graphs
• NP-completeness of local colorings of graphs
• The complexity of satisfiability problems
• A generalization of Kneser's conjecture

This page was built for publication: On the complexity of graph coloring with additional local conditions