• 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