On the \(b\)-dominating coloring of graphs (Q2576347): Difference between revisions

The \(b\)-chromatic number \(\varphi(G)\) of a graph \(G\) is the largest number \(k\) such that vertices of \(G\) can be coloured with \(k\) colours satisfying the following property: for each \(i\), \(1 \leq i \leq k\), there exists a vertex \(x_i\) of colour \(i\) such that for each \(j \neq i\), \(1 \leq j \leq k\) there exists a vertex \(y_j\) of colour \(j\) adjacent to \(x_i\). A graph \(G\) is called \(b\)-perfect if \(\varphi(G) = \chi(G)\) for each induced subgraph \(H\) of \(G\). In this paper, a characterization of \(b\)-perfect bipartite graphs is given; it is proved that a bipartite graph is \(b\)-perfect if and only if it is \(P_5\)-free, \(3P_3\)-free and \((P_4+P_3)\)-free (where ``\(+\)'' stands for the union of graphs). Further, it is proved that if a graph is \(2K_2\)-free and \(\overline{P_5}\)-free, then it is \(b\)-perfect. Also, the characterization of \(b\)-perfect \(P_4\)-sparse graphs (that is, the graphs with the property that no subset on five vertices contains more than one \(P_4\) as an induced subgraph) is given: a \(P_4\)-sparse graph is \(b\)-perfect if and only if it is \(2K_4^-\)-free, \(3P_3\)-free and \((P_4 + P_3)\)-free (where \(K_4^-\) is the graph \(K_4\) without an edge).