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 (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