کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648106 1342393 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
bb-colouring outerplanar graphs with large girth
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
bb-colouring outerplanar graphs with large girth
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1796–1803
نویسندگان
, ,