Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648106 | Discrete Mathematics | 2012 | 8 Pages |
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 kk such that the graph has a bb-colouring with kk colours. We show here how to compute in polynomial time the bb-chromatic number of an outerplanar graph of girth at least 88. This generalizes the seminal result of Irving and Manlove on trees.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frédéric Maffray, Ana Silva,