@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",
}