Locally identifying coloring in bounded expansion classes of graphs |
| |
Authors: | Daniel Gonçalves Aline Parreau Alexandre Pinlou |
| |
Institution: | 1. LIRMM - Univ. Montpellier 2, CNRS - 161 rue Ada, 34095 Montpellier Cedex 5, France;2. LIFL - Univ. Lille 1, INRIA - Parc scientifique de la haute borne, 59650 Villeneuve d’Ascq, France |
| |
Abstract: | A proper vertex coloring of a graph is said to be locally identifying if the sets of colors in the closed neighborhood of any two adjacent non-twin vertices are distinct. The lid-chromatic number of a graph is the minimum number of colors used by a locally identifying vertex-coloring. In this paper, we prove that for any graph class of bounded expansion, the lid-chromatic number is bounded. Classes of bounded expansion include minor closed classes of graphs. For these latter classes, we give an alternative proof to show that the lid-chromatic number is bounded. This leads to an explicit upper bound for the lid-chromatic number of planar graphs. This answers in a positive way a question of Esperet et al. L. Esperet, S. Gravier, M. Montassier, P. Ochem, A. Parreau, Locally identifying coloring of graphs, Electron. J. Combin. 19 (2) (2012)]. |
| |
Keywords: | Bounded expansion classes Minor-closed classes Planar graphs Locally identifying chromatic number |
本文献已被 ScienceDirect 等数据库收录! |
|