# Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that

(Hadw): $K_{\chi(G)}$ is a minor of $G$.

It turns out that for finite graphs, (Hadw) is equivalent to the following statement:

If $G$ is not a complete graph, then there is a minor $M$ of $G$ such that

1. $M \not \cong G$, and
2. $\chi(M) = \chi(G)$.

(For an explation of the equivalence of (Hadw) and (Hadw2) in the finite case, see this.)

It is easy to see that (Hadw) fails for graphs with infinite chromatic number: $G:=\bigcup_{n\in\omega} K_n$ has chromatic number $\omega$, but $K_\omega$ is not a minor of $G$.

Question: Is (Hadw2) also false for graphs with infinite chromatic number?

• Is there an easy example? (I got 2 +votes and 2 -votes, plus one close-vote, people seem quite divided on whether this is a valid question or rubbish). – Dominic van der Zypen Oct 23 '15 at 15:20

First, suppose $G$ has a connected component $C\subseteq G$ with the same chromatic number as $G$. If $C\neq G$, we can take $M=C$. If $G=C$, let $M$ be the subgraph of $G$ obtained by removing all edges involving some fixed vertex $v\in G$.

Now suppose $G$ has no connected component with the same chromatic number as $G$. It follows that we can choose an collection of connected components $C_i$ of $G$ such that each $C_i$ has a different chromatic number and $\chi(G)=\sup_i \chi(C_i)$. You can now let $M$ be the union of all but one of the $C_i$.

• Can't you simplify the argument slightly? If $G$ has isolated vertices, remove them all, and obtain a subgraph $M$ with no isolated vertices. If $G$ has no isolated vertices, remove all edges incident with some fixed vertex $v,$ and obtain a subgraph $M$ with one isolated vertex. – bof Oct 24 '15 at 1:44
• Looks good to me. – Eric Wofsey Oct 24 '15 at 1:50