@inproceedings{34f9ebb50f2649a7b2baba0a0c09d3bc,

title = "Local coloring: New observations and new reductions",

abstract = "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 every set of 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 show that it cannot be solved in subexponential time, unless the Exponential Time Hypothesis fails, and a new reduction for the NP-hardness of this problem. Our structural observations behind these reductions are of independent interests. We close the paper with a short remark on local colorings of perfect graphs.",

author = "Jie You and Yixin Cao and Jianxin Wang",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-18126-0_5",

language = "English",

isbn = "9783030181253",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "51--62",

editor = "Mei Lu and Yijia Chen and Xiaotie Deng",

booktitle = "Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings",

note = "13th International Workshop on Frontiers in Algorithmics, FAW 2019 ; Conference date: 29-04-2019 Through 03-05-2019",

}