Reading the Wikipedia article about Hadwiger's conjecture, I found this open problem really interesting. In this article it is written that
"in a minimal $k$-coloring of any graph $G$, contracting each color class of the coloring to a single vertex will produce a complete graph $K_k$. However, this contraction process does not produce a minor of $G$ because there is (by definition) no edge between any two vertices in the same color class, thus the contraction is not an edge contraction (which is required for minors). Hadwiger's conjecture states that there exists a different way of properly edge contracting sets of vertices to single vertices, producing a complete graph $K_k$, in such a way that all the contracted sets are connected."
Let's define the notion of "complete chromatic path" of an undirected graph $G$ in the following way:
the $n$-tuple $L(C):=(x_1, x_2,..., x_n)$ is called a "$C$-complete chromatic path" of $G$ if:
1) $k+1\le n$, where $k$ is the chromatic number of $G$
2) for all $1\leq i\leq n$, $x_i$ is a vertex of $G$
3) $x_1$ and $x_n$ share the same colour $C$
4) for all $2\le i\le n-1$, the colour of $x_i$ is different from $C$
5) whatever the colour $C'$ different from $C$, there exists $2\le i\le n-1$ such that the colour of $x_i$ is $C'$
6) for all $1\leq i\le n-1$, there is an edge that connects $x_i$ and $x_{i+1}$.
Does there exist a $C$-complete chromatic path for every colour $C$ used in a minimal coloring of $G$?
If so, let's go one step further adding a new set of $n-2$ vertices $\{x'_2,...x'_{n-1}\}$ to $G$ to form the "duplicata" of $L(C)$ defined as the $n$-tuple $(x_1,x'_2,...,x'_{n-1},x_{n})$, with $x'_i$ having the same colour than $x_i$ for all $2\le i\le n-1$, and let's connect $x_1$ to $x'_2$, $x'_{n-1}$ to $x_n$ and $x'_i$ to $x'_{i+1}$ for all $2\le i\le n-2$.
Let's do this for all $C$-complete chromatic paths when $C$ runs through the $k$ colours used to color $G$, and finally let's realize edge contractions for all the edges of $L(C)$ when $C$ runs through the $k$ colours used to color $G$. I think the resulting graph $G'$ is (isomorphic to) a minor of $G$ that contains exactly one vertex of each colour, each of these vertices being connected to each other.
What do you think of this approach? Could it lead to some progress towards the proof of Hadwiger's conjecture or is it hopeless?
