Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/40706
Title in Portuguese: b-Coloring graphs with large girth
Title: b-Coloring graphs with large girth
Author: Campos, Victor Almeida
Farias, Victor Aguiar Evangelista de
Silva, Ana Shirley Ferreira da
Keywords: b-Chromatic number
b-Coloring
m-Degree
Girth
Exact algorithm
Issue Date: 2012
Publisher: Journal of The Brazilian Computer Society
Citation: CAMPOS, Victor Almeida; FARIAS, Victor Aguiar Evangelista de; SILVA, Ana Shirley Ferreira da. b-Coloring graphs with large girth. Journal of The Brazilian Computer Society, v. 18, p. 2012-375-378, 2012.
Abstract: A b-coloring of a graph is a coloring of its vertices such that every color class contains a vertex that has a neighbor in all other classes. The b-chromatic number of a graph is the largest integer k such that the graph has a b-coloring with k colors. We show how to compute in polynomial time the b-chromatic number of a graph of girth at least 9. This improves the seminal result of Irving and Manlove on trees
URI: http://www.repositorio.ufc.br/handle/riufc/40706
Appears in Collections:DMAT - Artigos publicados em revista científica

Files in This Item:
File Description SizeFormat 
2012_art_vacampos.pdf142,58 kBAdobe PDFView/Open


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