For any simple, undirected graph $G=(V,E)$ where $V$ is finite, we define the Hadwiger number $\eta(G)$ to be the maximum $n$ such that $K_n$ is a minor of $G$.

Is there a graph $G$ on such that removing a vertex or contracting an edge reduces the chromatic number, but has no effect on the Hadwiger number?

To be more precise, I'm looking for a graph $G$ such that

  1. $G$ is vertex-critical (for any $v\in V(G)$ we have $\chi(G\setminus\{v\}) = \chi(G) - 1$);
  2. $G$ is edge-contraction-critical (for any $e\in E(G)$ contracting $e$ reduces the chromatic number);
  3. for any $v\in V(G)$ we have $\eta(G) = \eta(G\setminus \{v\})$;
  4. for any $e\in E(G)$ contracting $e$ does not change the Hadwiger number.

Here's an example that does not require a computer or exercises left to the reader. Let $G$ be the graph obtained by taking two $7$-cycles $C_1$ and $C_2$ and joining each vertex of $C_1$ to each vertex of $C_2$. The chromatic number of this graph is $6$ since $\chi(C_1)=\chi(C_2)=3$. The Hadwiger number of this graph is $7$ (we get a $K_7$ by contracting a perfect matching between $V(C_1)$ and $V(C_2))$. Deleting a vertex yields a path on one side, so the chromatic number goes down to $5$. Contracting an edge of $C_1$ or $C_2$ gives a $6$-cycle on one side, so the chromatic number goes down to $5$. Contracting an edge between $V(C_1)$ and $V(C_2)$ yields two $7$-cycles $C_1'$ and $C_2'$ meeting at a vertex $v$, together with all edges between $V(C_1') \setminus v$ and $V(C_2') \setminus v$. This graph is obviously $5$-colourable, since there is a $3$-colouring of $C_1'$ where only $v$ is coloured red. Finally, deleting a vertex or contracting an edge does not change the Hadwiger number, since in either case the resulting graph still contains $K_{6,7}$. Contracting a matching of size $6$ in $K_{6,7}$ yields a $K_7$-minor.

Edit. Having read my answer again after a few years, I see a mistake in the above argument. The Hadwiger number of $G$ is actually $8$ (not $7$ as claimed), since contracting the edges of a matching of size $6$ between $V(C_1)$ and $V(C_2)$ yields a $K_8$-minor. Thus, the Hadwiger number of $G$ appears to go down when contracting an edge of $C_1$ or $C_2$.


Here's one for you:

enter image description here

Although it is not drawn planar, it is planar, and so it has no $K_5$-minor. However it has lots of $K_4$-minors. For example, the $0,4,6,8$ induces $K_4\backslash e$ and so adding any path from $4$ to $6$, say $4-7-1-6$ gives a graph that can be contracted to $K_4$. So this shows that deleting $2$ or $3$ or $5$ still leaves a $K_4$-minor. The remaining cases are similar and left as an exercise!

As for the colouring, it is easy to see that it is not $3$-colourable just by working with the triangles (start with $0$ red, $6$ green and $8$ blue and follow your nose). But contracting any edge leaves a $3$-chromatic graph.

You can see this easily enough by hand, or just run this code:

g = Graph("H?`vAqz")
for e in g.edges():
    h = copy(g)
    print h.chromatic_number()

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.