Is there a known upper bound on the minimum number of vertices in a graph with girth 5 and chromatic number $k$? Could you also give references for this?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I believe there's a construction based on random Cayley graphs of $PGL_2(n)$: assign $n^\frac52$ colors uniformly random to the elements of $PGL_2(n)$, such that $a$ and $a^{-1}$ have same colors. By counting monochromatic cycles, there's a girth-5 graph induced by some color with high probablity. Now one should compute the spectral gap and use the Hoffman chromatic bound to conclude that $χ$ grows like $Ω(n^α)$, thus establishing a polynomial bound. $\endgroup$– LeechLatticeAug 17, 2019 at 15:18
Add a comment
|