1
$\begingroup$

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

We say that a finite, simple, undirected graph $G=(V,E)$ is contraction-sensitive if collapsing any $2$ non-adjacent points increases the Hadwiger number. An example of such a graph is the icosahedron.

Is there an established term for what I call "contraction-sensitive", and is there any literature on it? In particular it would be interesting to know whether there such graphs that are in addition vertex-critical (that is, removing any vertex decreases the chromatic number).

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .