2
$\begingroup$

This is an exercise from chapter 7 of Diestel's 'Graph theory':

Show that there exists a function $f$ such that each graph $G$ of chromatic number at least $f(r)$ contains a $K_r$ minor.

My attempts Use induction on $r$.

I try to find a vertex $u\in V(G)$ such that $N(u)$ induces a subgraph whose chromatic number is at least $f(r-1)$.

Pick an arbitrary vertex $v$. We may assume that $\chi(G-v)=f(r)-1$, otherwise eliminate $v$ and continue with $G-v$. Now, in any vertex coloring of $G$, $N(u)$ uses $f(r)-1$ colors. However, this may be due to some structure in $G-(\{u\}\cup N(u))$. And I am stuck here.

Additional information that may be useful

Some references attribute a result to Klaus Wagner in 1964. Seemingly this well-known mathematician wrote few English articles and I even failed to find his original paper.

Note that this is only an exercise and I post it here deliberately instead of overflow. Recent progress on this conjecture is welcomed but that's not my purpose.

Thanks!

$\endgroup$
3
  • $\begingroup$ The usual (as far as I know) way to prove this is in two steps: 1) you prove that any graph with chromatic number $k$ contains a subgraph with min degree at least $k-1$, or said otherwise, a $k$-degenerate graph has chromatic number at most $k + 1$. I think this is done by induction on the number of vertices. 2) Then the second step is Mader theorem, every graph with large average degree contains a complete minor. $\endgroup$ Commented Aug 4, 2023 at 0:24
  • $\begingroup$ FYI, Wagner and Mader Theorem should be both in Diestel. $\endgroup$ Commented Aug 4, 2023 at 0:26
  • $\begingroup$ Thanks for your comment @ThomasLesgourgues. That helped me to come up with a valid proof! It occurs that Diestel removes Mader's theorem (1967) from exercises in chapter 7 in the 5th edition, but I somehow found it in the 3rd edition (2006). Besides, in the 5th edition, exercises that aim for proof of a named theorem no longer mention the name as RD wrote in the preface. Again, thanks for your hint! $\endgroup$ Commented Aug 4, 2023 at 6:34

1 Answer 1

2
$\begingroup$

This answer is fully inspired by @Thomas Lesgourgues.

Lemma A graph $G$ in which $|E(G)|\geq 2^{k-3}|V(G)|$ contains a $K_k$-minor.

Proof

If $G$ has some edge $e$ included in less than $2^{k-3}$ triangles, then $E(G/e)\geq 2^{k-3}V(G)-2^{k-3}=2^{k-3}(V(G)-1)$. Hence, we switch to $G/e$ to find a $K_k$-minor. Noted that this cannot always happen, so we will arrive at some graph $G$ where each edge $e$ lies in at least $2^{k-3}$ triangles.

Let $t(e)$ be the number of triangles that contain $e$. We have a crucial observation: $$\sum_{v\in V}|E(G[N(v)])|=\sum_{e\in E(G)}t(e)\geq 2^{t-3}|E(G)|=2^{t-4}\sum_{v\in V}d(v).$$

The first '=' comes from the double counting of $$\{(v,e)\in V\times E:\text{$v$ is the opposite vertex to $e$ in some triangel}\}.$$

Thus, we come up with some vertex $v$ such that $H=G[N(v)]$ satisfies $|E(H)|\geq 2^{k-4}d(v)$. Hence, we may apply induction on $k$ to discover a $K_{k-1}$-minor in $H$ and come up with a $K_k$-minor in $G$ together with $v$.

Lemma A graph $G$ whose chromatic number is at least $k$ contains a subgraph $H$ where $\delta(H)\geq k-1$.

Proof

Keep removing vertices in $G$ to obtain a $k$-critical subgraph $H$.

In the end, we derive

Theorem Every $(2^{k-2}+1)$-chromatic graph has a $K_k$ minor.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .