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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ A complete graph works vacuously. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 18, 2019 at 22:02
  • $\begingroup$ Thanks - will exclude this in the question! $\endgroup$
    – Dominic van der Zypen
    Commented 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
    Commented Apr 19, 2019 at 6:53

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .