Recolouring-resistant colourings

Autor: Dieter Rautenbach, Anders Sune Pedersen
Rok vydání: 2011
Předmět:
Zdroj: Pedersen, A S & Rautenbach, D 2011, ' Recolouring-resistant colourings ', Discrete Applied Mathematics, vol. 159, no. 10, pp. 1013-1021 . https://doi.org/10.1016/j.dam.2011.02.002
ISSN: 0166-218X
DOI: 10.1016/j.dam.2011.02.002
Popis: We study colourings of graphs with the property that the number of used colours cannot be reduced by applying some recolouring operation. A well-studied example of such colourings are b-colourings, which were introduced by Irving and Manlove [R.W. Irving, D.F. Manlove, The la-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141]. Given a graph and a colouring, a recolouring operation specifies a set of vertices of the graph on which the colouring can be changed. We consider two such operations: One which allows the recolouring of all vertices within some given distance of some colour class, and another which allows the recolouring of all vertices that belong to one of a given number of colour classes. Our results extend known results concerning b-colourings and the associated b-chromatic number. (C) 2011 Elsevier B.V. All rights reserved.
Databáze: OpenAIRE
Externí odkaz: