Title of article
b-colouring outerplanar graphs with large girth
Author/Authors
Maffray، Fredric نويسنده , Silva، Ana نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2012
Pages
8
From page
1796
To page
1803
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 k such that the graph has a b -colouring with k colours. We show here how to compute in polynomial time the b -chromatic number of an outerplanar graph of girth at least 8 . This generalizes the seminal result of Irving and Manlove on trees.
Keywords
Outerplanar graphs , Exact algorithm , b -colouring , b -chromatic number
Journal title
Discrete Mathematics
Serial Year
2012
Journal title
Discrete Mathematics
Record number
1599978
Link To Document