Local Coloring and its Complexity
share
A k-coloring of a graph is an assignment of integers between 1 and k to vertices in the graph such that the endpoints of each edge receive different numbers. We study a local variation of the coloring problem, which imposes further requirements on three vertices: We are not allowed to use two consecutive numbers for a path on three vertices, or three consecutive numbers for a cycle on three vertices. Given a graph G and a positive integer k, the local coloring problem asks for whether G admits a local k-coloring. We give a characterization of graphs admitting local 3-coloring, which implies a simple polynomial-time algorithm for it. Li et al. [http://dx.doi.org/10.1016/j.ipl.2017.09.013Inf. Proc. Letters 130 (2018)] recently showed it is NP-hard when k is an odd number of at least 5, or k = 4. We show that it is NP-hard when k is any fixed even number at least 6, thereby completing the complexity picture of this problem. We close the paper with a short remark on local colorings of perfect graphs.
READ FULL TEXT