{"id":"arxiv/2606.29873","url":"https://arxiv.org/abs/2606.29873","tags":["math.CO"],"score":0,"title":"On a problem of Sivaraman and a problem of Gyárfás","domain":"math.CO","source":"arxiv","authors":["Kaiyang Lan","Wenlong Zhong"],"reviews":0,"subject":"math.CO","summary":"The \\textit{girth} of a graph $G$, denoted $\\mathrm{g}(G)$, is the length of a shortest cycle in $G$. If $G$ contains no cycle, we define $\\mathrm{g}(G)=\\infty$. Sivaraman (2020) asked for the optimal $χ$-bounding function for the class of graphs whose complements have girth at least $6$. Let \\(F(s) = \\max\\{χ(G): ω(G)\\le s,\\ \\mathrm{g}(\\overline{G})\\ge 6\\}\\). We prove that there exists a constant \\(c>0\\) such that \\[ c\\left(\\frac{s}{\\log s}\\right)^{4/3} \\le F(s) \\le (1+o(1))\\frac{s^{3/2}}{\\log s}. \\] For small values, we establish the exact results \\[ F(1)=1,\\; F(2)=2,\\; F(3)=4,\\; F(4)=5,\\;…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-29","reactions":{}}