NP-completeness of local colorings of graphs

DOI10.1016/j.ipl.2017.09.013zbMath1419.68055OpenAlexW2759840798MaRDI QIDQ1679905

Zepeng Li, Zehui Shao, Jin Xu, En-Qiang Zhu

Publication date: 22 November 2017

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.09.013

zbMATH Keywords

computational complexityNP-completeplanar graphlocal chromatic numberlocal \(k\)-coloring

Mathematics Subject Classification ID

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

Related Items (2)

On the complexity of graph coloring with additional local conditions ⋮ A note on local coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on local coloring of graphs
• Local coloring of Kneser graphs
• Coloring graphs with locally few colors
• Reducibility among Combinatorial Problems
• Local colourings of Cartesian product graphs
• The complexity of theorem-proving procedures
• A generalization of Kneser's conjecture

This page was built for publication: NP-completeness of local colorings of graphs