Critical with respect to chromatic, but not Hadwiger number

Question

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.

Answer 1

Here's one for you:

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)
    h.merge_vertices([e[0],e[1]])
    print h.chromatic_number()

Answer 2

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