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}$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.14517
curl -X POST /api/v1/records/arxiv/2608.14517/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.14517/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'