کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420330 | 683924 | 2011 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Applied Mathematics - Volume 159, Issue 1, 6 January 2011, Pages 60–68