{"id":"arxiv/2606.07461","url":"https://arxiv.org/abs/2606.07461","tags":["math.CO"],"score":0,"title":"Improved bounds on the b-chromatic number using the independence and chromatic numbers","domain":"math.CO","source":"arxiv","authors":["Manouchehr Zaker"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-05","reactions":{}}