2018/09/07 by Jie You, Yixin Cao, You, Jie +3
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.1809.02513
openalex publication_date 2018/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.~[\hrefhttp://dx.doi.org/10.1016/j.ipl.2017.09.013 Inf.~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.