NP-completeness of local colorings of graphs
From MaRDI portal
Publication:1679905
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
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On the complexity of graph coloring with additional local conditions, A note on local coloring of graphs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item