Consider the following statement:

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

  1. $M \not \cong G$, and
  2. there is a graph homomorphism $f:G\to M$.

Hadwiger's conjecture states that for every finite simple undirected graph $G$, the complete graph $K_{\chi(G)}$ is a minor of $G$. Since colorings $G$ are homorphisms from $G$ to some complete graphs, it is not hard to see that in the finite case, Hadwiger's conjecture is equivalent to (S). Now, the statement of Hadwiger's conjecture is false for graphs with infinite chromatic number (see for example the disjoint union of all $K_n, n\in\mathbb{N}$).

Question. Does statement (S) hold for graphs with infinite chromatic number?

(This is a follow-up to this question.)


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.