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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .