Bounds for the smallest k-chromatic graphs of given girth

05/17/2018
by   Geoffrey Exoo, et al.
0

Let n_g(k) denote the smallest order of a k-chromatic graph of girth at least g. We consider the problem of determining n_g(k) for small values of k and g. After giving an overview of what is known about n_g(k), we provide some new lower bounds based on exhaustive searches, and then obtain several new upper bounds using computer algorithms for the construction of witnesses, and for the verification of their correctness. We also present the first examples of reasonably small order for k = 4 and g > 5. In particular, the new bounds include: n_4(7) ≤ 77, 26 ≤ n_6(4) ≤ 66, 30 ≤ n_7(4) ≤ 171.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset