Improved bounds on the b-chromatic number using the independence and chromatic numbers
A b-coloring of a graph $G$ is a proper vertex coloring where each color class contains at least one vertex (a b-vertex) adjacent to a vertex in every other color class. The maximum number of colors in such a coloring is the b-chromatic number, ${\rm b}(G)$. A ${\rm b}^{\ast}$-coloring is a variation in which a b-vertex is adjacent to a b-vertex in every other color class. We employ the ${\rm b}^{\ast}$-coloring to prove that any $n$-vertex graph $G$ with independence number at most $t$ satisfies ${\rm b}(G) \leq [(t-1)n+tχ(G)]/(2t-1)$. This bound extends the bounds of Kouider and Zaker…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.07461
curl -X POST /api/v1/records/arxiv/2606.07461/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.07461/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'