Show that for each constant $c$, for sufficiently large $n$ (with respect to $c$) there is a graph $G=(V,E)$ with $n$ vertices and bounded (constant which depends on $c$) degree $d$ such that $G$ has no coloring of size $c$ AND $G$ has no cycles of length smaller than $O(\log(n))$.
My idea is to randomly choose appropriate graph drawn from $G(n,p)$ and then remove the "exceeding" edges in order to get bounded degree - but if I do so the chromatic number may change.
Any ideas?


It is known that there are triangle-free graphs with arbitrary large chromatic number, so called Mycielski graphs. This idea was further generalized to build graphs with higher girth and arbitrary high chromatic number.

  • $\begingroup$ thanks, but I believe that this approach is overkill. It is possible to prove that there exist such graph with given girth $g$ and chromatic number at least $k$ by looking at $G(n,p)$ with $p = n^{(1-g)/g}$, show that there aren't much cycles of size larger than $g$ ($n/2$) AND that the size of maximal independent set isn't too large. Removing one node from each cycle and using that fact that chromatic number is connected with maximal independent set solves it. But the degree constraint isn't guaranteed $\endgroup$ – Georege Jun 23 '17 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.