b-continuity and Partial Grundy Coloring of graphs with large girth

Abstract

A b-coloring of a graph is a proper coloring such that each color class has at least one vertex which is adjacent to each other color class. The b-spectrum of $G$ is the set $S_b(G)$ of integers $k$ such that $G$ has a b-coloring with $k$ colors and $b(G)=\max S_b(G)$ is the b-chromatic number of $G$. A graph is b-continous if $S_b(G)=[\chi (G),b(G)]\cap \mathbb{Z}$. An infinite number of graphs that are not b-continuous is known. It is also known that graphs with girth at least 10 are b-continuous. A partial Grundy coloring is a proper coloring $f:V(G)\to \{1,\dots ,k\}$ such that each color class $i$ contains some vertex $u$ that is adjacent to every color class $j$ such that $j<i$. The partial Grundy number of $G$ is the maximum value $\partial \Gamma (G)$ for which $G$ has a partial Grundy coloring. In this work, we prove that graphs with girth at least 8 are b-continuous, and that the b-spectrum of a graph $G$ with girth at least 7 contains the integers between $2\chi (G)$ and $b(G)$. We also prove that $\partial \Gamma (G)$ equals a known upper bound when $G$ is a graph with girth at least 7. These results generalize previous ones by Linhares-Sales and Silva (2017), and by Shi et al.(2005).

11 pages; 4 figures; partially presented at LAGOS'19