A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Locally identifying colourings for graphs with given maximum degree
Tekijät: Foucaud F, Honkala I, Laihonen T, Parreau A, Perarnau G
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2012
Journal: Discrete Mathematics
Tietokannassa oleva lehden nimi: DISCRETE MATHEMATICS
Lehden akronyymi: DISCRETE MATH
Numero sarjassa: 10
Vuosikerta: 312
Numero: 10
Aloitussivu: 1832
Lopetussivu: 1837
Sivujen määrä: 6
ISSN: 0012-365X
DOI: https://doi.org/10.1016/j.disc.2012.01.034
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/2227592
A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u, v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of u and v are different. We show that any graph G has a locally identifying colouring with 2 Delta(2) - 3 Delta + 3 colours, where Delta is the maximum degree of G, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs. (c) 2012 Elsevier B.V. All rights reserved.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
