Inapproximability of the lid-chromatic number

详细信息    查看全文

• 作者：Nicolas Martins¹ ; ^{nicolasam@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini Sampaio¹ ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Locally identifying coloring ; inapproximability ; cographs ; P4P4-sparse graphs
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：50
• 期：Complete
• 页码：121-126
• 全文大小：189 K

文摘

A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv where u and v have distinct closed neighborhoods, the set of colors used on vertices of the closed neighborhoods of u and v are also distinct. In this paper we obtain 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 P₄'s. We also prove that the lid-chromatic number is O(n^1/2−ε)$O(n^{1/2-\epsilon })$-inapproximable in polinomial time for every ε>0$\epsilon >0$, unless P=NP.