Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/40706| Type: | Artigo de Periódico |
| Title: | b-Coloring graphs with large girth |
| Title in English: | b-Coloring graphs with large girth |
| Authors: | Campos, Victor Almeida Farias, Victor Aguiar Evangelista de Silva, Ana Shirley Ferreira da |
| Keywords: | Coloração de grafos;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. 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 |
| Access Rights: | Acesso Aberto |
| Appears in Collections: | DMAT - Artigos publicados em revista científica |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2012_art_vacampos.pdf | 142,58 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.