首页 | 本学科首页   官方微博 | 高级检索  
     


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 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:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号