0
$\begingroup$

Is there a connected, finite, simple, undirected, and non-complete graph $G=(V,E)$ such that whenever an independent subset $J\subseteq V$ with $|J|>1$ is collapsed, the Hadwiger number of the resulting graph is larger than the Hadwiger number $\eta(G)$ of $G$?

EDIT. Excluded complete graphs; thanks to Ilya Bogdanov for his comment below.

$\endgroup$
  • 1
    $\begingroup$ A complete graph works vacuously. $\endgroup$ – Ilya Bogdanov Apr 18 at 22:02
  • $\begingroup$ Thanks - will exclude this in the question! $\endgroup$ – Dominic van der Zypen Apr 19 at 6:15
  • 1
    $\begingroup$ Such a graph would also yield a positive answer to this question of yours mathoverflow.net/questions/290435/… (same question of existence, with a weaker condition), so better stay with the other one first. BTW I would intuitively think that both are equivalent, but that might be a different question! $\endgroup$ – Wolfgang Apr 19 at 6:53

Your Answer

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

Browse other questions tagged or ask your own question.