On the b-continuity of the lexicographic product of graphs

Abstract

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of $G$ is the maximum integer ${\chi }_b(G)$ for which $G$ has a b-coloring with ${\chi }_b(G)$ colors. A graph $G$ is b-continuous if $G$ has a b-coloring with $k$ colors, for every integer $k$ in the interval $[\chi (G),{\chi }_b(G)]$. It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product $G[H]$ of b-continuous graphs $G$ and $H$ is also b-continuous. Using homomorphisms, we provide a new lower bound for ${\chi }_b(G[H])$, namely ${\chi }_b(G[K_t])$, where $t={\chi }_b(H)$, and prove that if $G[K_{\ell }]$ is b-continuous for every positive integer $\ell$, then $G[H]$ admits a b-coloring with $k$ colors, for every $k$ in the interval $[\chi (G[H]),{\chi }_b(G[K_t])]$. We also prove that $G[K_{\ell }]$ is b-continuous, for every positive integer $\ell$, whenever $G$ is a $P_4$-sparse graph, and we give further results on the b-spectrum of $G[K_{\ell }]$, when $G$ is chordal.