Inapproximability of the lid-chromatic number
| Autor: | Rudini Menezes Sampaio, Nícolas A. Martins |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Physics::Computational Physics
Discrete mathematics Applied Mathematics Complete coloring Nonlinear Sciences::Cellular Automata and Lattice Gases Graph Physics::Geophysics Physics::Fluid Dynamics Greedy coloring Combinatorics Edge coloring Discrete Mathematics and Combinatorics Chromatic scale Fractional coloring Time complexity Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 50:121-126 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2015.07.021 |
| Popis: | 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 P4's. We also prove that the lid-chromatic number is O ( n 1 / 2 − e ) -inapproximable in polinomial time for every e > 0 , unless P=NP. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect