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

Abstract

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.

Disclosure

“Moreover, setting k = 4d − 1 gives χ= (Gd,4d−1 )/L(Gd,4d−1 ) = (5d − 1)/(4d − 1) → 5/4 as d → ∞. Acknowledgments. The author thanks the anonymous referee for helpful comments that improved the presentation of the results. Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work, the author used OpenAI ChatGPT in order to assist with language editing and manuscript polishing. After using this tool, the author rev”

PDF page 5

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T05:15:51.285882Z

Structural counts