2
$\begingroup$

This is an update to an older question admitting a trivial example to answer it.

Suppose $G$ is a finite simple graph. Let $h(G)$ denote the Hadwiger number of $G$; that is, the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.

Given an integer $n \geq 3$, is there a graph $G = (V,E)$ with $\chi(G) = n$ and with the following property?

There are two non-adjacent vertices $v, w\in V$ such that when $v$ and $w$ are identified, the Hadwiger number of the resulting graph is smaller than $h(G)$.

$\endgroup$
2
$\begingroup$

This is a generalization of Bjørn Kjos-Hanssen's answer to your previous question.

Take $K_{n+2}$ and remove two edges between two different pairs of vertices, say $(1,2)$ and $(3,4)$ The chromatic number is $n$. The Hadwiger number is $n$ as well. But if we identify 1 and 3, we get $K_{n+1}$ with Hadwiger number $n+1$.

$\endgroup$

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.