Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950770 | Information Processing Letters | 2018 | 6 Pages |
Abstract
A local k-coloring of a graph G is a function f:V(G)â{1,2,â¯,k} such that for each SâV(G), 2â¤|S|â¤3, there exist u,vâS with |f(u)âf(v)| at least the size of the subgraph induced by S. The local chromatic number of G is Ïâ(G)=minâ¡{k:G has a local k-coloring}. In this paper, we show 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. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree Î=7 or 8.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zepeng Li, Enqiang Zhu, Zehui Shao, Jin Xu,