A disproof of a gap-one conjecture for the equitable chromatic number of block graphs

Abstract

For a graph $G$, let $L(G)=\max \{\omega (G),\lceil (|V(G)|+1)/({\alpha }_{\min }(G)+1)\rceil \}$, where $\omega (G)$ is the clique number and ${\alpha }_{\min }(G)$ is the minimum, over all vertices $v$, of the largest size of an independent set containing $v$. Dybizbański, Furmańczyk, and Mkrtchyan (Discrete Appl. Math. 354 (2024), 15--28) conjectured that every block graph $G$ satisfies $L(G)\le {\chi }_{=}(G)\le L(G)+1$, where ${\chi }_{=}(G)$ is the equitable chromatic number of $G$. We disprove this conjecture in a strong form. For every pair of integers $d\ge 2$ and $k\ge 4d-1$, we construct a connected block graph $G_{d,k}$ such that $L(G_{d,k})=k$ and ${\chi }_{=}(G_{d,k})=k+d$. Thus the difference ${\chi }_{=}(G)-L(G)$ is unbounded on connected block graphs.

6 pages