I am trying to show that for any $n$, any graph of sufficiently large chromatic number contains $K_n$ as a minor. In other words, there exists a (minimal) function $f$ such that $\chi_G(n)\geq f(n)\implies G$ contains a $K_n$-minor. I'd then like to show that $f(n)\geq \frac12 \,f(n+1)$.

I'm totally stuck and can't see where to start, and would appreciate some help or a hint.

  • $\begingroup$ What makes you think it's true? Is it stated in some book? Can you give the reference? I don't know how to prove it, but I'm not sure I like your idea of first proving the existence and "then" proving the inequality. If I was going to try to work that exercise, I'd try to prove that if every $m$-chromatic graph has a $K_n$-minor then every $2m$-chromatic graph has a $K_{n+1}$-minor, thus proving both the existence of $f(n)$ (by induction) and the inequality. However, I don't know how to do that. $\endgroup$ – bof Mar 11 '17 at 3:51
  • $\begingroup$ @bof Yes. I did some digging online and it was proved in 1964 by someone named Wagner. I haven't been able to get my hands on the original paper though (and even then, it would be in German). And that does sound like an efficient approach, I didn't think of that. $\endgroup$ – Sonk Mar 11 '17 at 4:03

Your Answer

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

Browse other questions tagged or ask your own question.