4
$\begingroup$

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

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .