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.