Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875725 | Theoretical Computer Science | 2018 | 8 Pages |
Abstract
A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the set of colors used on vertices of the closed neighborhoods of u and v are distinct. The lid-chromatic number is the minimum number of colors used in a lid-coloring. In this paper we prove a relation between lid-coloring and a variation, called strong lid-coloring. With this, we obtain linear time algorithms to calculate the lid-chromatic number for some classes of graphs with few P4's, such as cographs, P4-sparse graphs and (q,qâ4)-graphs. We also prove that the lid-chromatic number is O(n1âε)-inapproximable in polynomial time for every ε>0, unless P=NP.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nicolas Martins, Rudini Sampaio,