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?

  • 7
    $\begingroup$ As stated, the question seems too close to "Here's an approach to an open problem; finish it for me or give me a hint so that I can finish it." For it to be appropriate for MathOverflow. Better would be "Here's an approach to an open problem; after looking at references X, Y, and Z, I have found nothing about the merits or demerits of the approach. Has anyone seen this, and can they give me a reference?", and I am sure even better versions exist. Try again. Gerhard "Email Me About System Design" Paseman, 2011.07.07 $\endgroup$ – Gerhard Paseman Jul 7 '11 at 20:49
  • $\begingroup$ To aid in parsing the above, replace "For it" by "for it". Apologies for the typo. Gerhard "Email Me About System Design" Paseman, 2011.07.07 $\endgroup$ – Gerhard Paseman Jul 8 '11 at 6:42
  • $\begingroup$ May (should?) also add some classes of graphs having a C-chromatic path for each C and some classes where the existence of such paths is less clear. $\endgroup$ – Jérôme JEAN-CHARLES Apr 27 '18 at 16:23

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.