کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420330 683924 2011 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the bb-coloring of P4P4-tidy graphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the bb-coloring of P4P4-tidy graphs
چکیده انگلیسی

A bb-coloring   of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The bb-chromatic number   of a graph GG, denoted by χb(G)χb(G), is the maximum number tt such that GG admits a bb-coloring with tt colors. A graph GG is bb-continuous   if it admits a bb-coloring with tt colors, for every t=χ(G),…,χb(G)t=χ(G),…,χb(G), and it is bb-monotonic   if χb(H1)≥χb(H2)χb(H1)≥χb(H2) for every induced subgraph H1H1 of GG, and every induced subgraph H2H2 of H1H1. In this work, we prove that P4P4-tidy graphs (a generalization of many classes of graphs with few induced P4P4s) are bb-continuous and bb-monotonic. Furthermore, we describe a polynomial time algorithm to compute thebb-chromatic number for this class of graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 1, 6 January 2011, Pages 60–68
نویسندگان
, , ,