Locally identifying coloring of graphs with few P4s
| Autor: | Rudini Menezes Sampaio, Nícolas A. Martins |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Physics::Computational Physics
Discrete mathematics General Computer Science 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Complete coloring Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Physics::Geophysics Theoretical Computer Science Brooks' theorem Physics::Fluid Dynamics Greedy coloring Combinatorics Edge coloring 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Graph coloring Fractional coloring Time complexity Mathematics List coloring |
| Zdroj: | Theoretical Computer Science. 707:69-76 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2017.10.015 |
| Popis: | 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 P 4 's, such as cographs, P 4 -sparse graphs and ( q , q − 4 ) -graphs. We also prove that the lid-chromatic number is O ( n 1 − e ) -inapproximable in polynomial time for every e > 0 , unless P = NP . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect