Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/78995
Type: Artigo de periódico
Title: Colouring Clique-Hypergraphs of Circulant Graphs
Author: Campos, CN
Dantas, S
de Mello, CP
Abstract: A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, , of a graph G has V(G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained.
Subject: Graph and hypergraph colouring
Clique-colouring
Circulant graphs
Powers of cycles
Country: Japão
Editor: Springer Japan Kk
Rights: fechado
Identifier DOI: 10.1007/s00373-012-1241-4
Date Issue: 2013
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.