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$
3
  • 1
    $\begingroup$ A complete graph works vacuously. $\endgroup$ Apr 18, 2019 at 22:02
  • $\begingroup$ Thanks - will exclude this in the question! $\endgroup$ Apr 19, 2019 at 6:15
  • 2
    $\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, 2019 at 6:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.