3
$\begingroup$

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:

(Hadw2):

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?

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – Dominic van der Zypen Oct 23 '15 at 15:20
2
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – bof Oct 24 '15 at 1:44
  • $\begingroup$ Looks good to me. $\endgroup$ – Eric Wofsey Oct 24 '15 at 1:50

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.