5
$\begingroup$

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?

$\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$ Aug 17, 2019 at 15:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.