{"id":"arxiv/2609.07014","url":"https://arxiv.org/abs/2609.07014","tags":["math.CO"],"score":0,"title":"Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Saieed Akbari","Arash Beikmohammadi"],"reviews":0,"subject":"math.CO","summary":"It was recently shown that every connected graph of order $n \\geq 5$ and size $m$ satisfies $χ(G) \\leq \\left\\lceil \\frac{m}{\\sqrt{n}} \\right\\rceil$, and it was asked whether the stronger inequality $χ(G) \\leq \\left\\lceil \\frac{m}{2\\sqrt{n}} \\right\\rceil + 1$ holds for every connected triangle-free graph. In this paper, we answer this question in the affirmative. In fact, we prove that every connected triangle-free graph $G$ with $G \\not\\cong C_5$ satisfies $χ(G) \\leq \\left\\lceil \\frac{m}{\\sqrt{5.5n}} \\right\\rceil + 1$, where the constant $\\sqrt{5.5}$ cannot be replaced by any constant…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}