A disproof of a gap-one conjecture for the equitable chromatic number of block graphs
For a graph $G$, let $L(G)=\max\{ω(G),\lceil (|V(G)|+1)/(α_{\min}(G)+1)\rceil\}$, where $ω(G)$ is the clique number and $α_{\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)\leqχ_{=}(G)\leq L(G)+1$, where $χ_{=}(G)$ is the equitable chromatic number of $G$. We disprove this conjecture in a strong form. For every pair of integers $d\geq 2$ and $k\geq 4d-1$, we construct a connected block graph $G_{d,k}$ such that $L(G_{d,k})=k$ and $χ_{=}(G_{d,k})=k+d$. Thus the difference $χ_{=}(G)-L(G)$ is unbounded on connected block graphs.
Comments
Log in to comment, reply, and vote.
No comments yet.