Name
Abstract | ||
|---|---|---|
•We study the local k-coloring of graphs.•We prove that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2t−1, where t≥3.•We prove that it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree Δ=7 or 8. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.ipl.2017.09.013 | Information Processing Letters |
Keywords | Field | DocType |
Local k-coloring,Local chromatic number,Planar graph,NP-complete,Computational complexity | Discrete mathematics,Combinatorics,Forbidden graph characterization,Graph power,Bound graph,Degree (graph theory),Universal graph,Windmill graph,Butterfly graph,Degeneracy (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
130 | C | 0020-0190 |
Citations | PageRank | References |
1 | 0.41 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zepeng Li | 1 | 20 | 9.07 |
| Enqiang Zhu | 2 | 25 | 11.99 |
| Zehui Shao | 3 | 119 | 30.98 |
| Jin Xu | 4 | 230 | 45.13 |