b-colouring outerplanar graphs with large girth |
| |
Authors: | Frédéric Maffray Ana Silva |
| |
Affiliation: | 1. CNRS, Laboratoire G-SCOP, Grenoble, France;2. Departamento de Matemática, UFC, Fortaleza, Brazil |
| |
Abstract: | A b-colouring of a graph is a colouring of its vertices such that every colour class contains a vertex that has a neighbour in all other classes. The b-chromatic number of a graph is the largest integer such that the graph has a -colouring with colours. We show here how to compute in polynomial time the -chromatic number of an outerplanar graph of girth at least . This generalizes the seminal result of Irving and Manlove on trees. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|