Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

last night I read the article of Wikipedia about Hadwiger's conjecture, and 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."

So 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?

Thank you in advance.

share|improve this question
4  
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 –  Gerhard Paseman Jul 7 '11 at 20:49
    
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 –  Gerhard Paseman Jul 8 '11 at 6:42
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.