Let $G=(V,E)$ be a finite, simple, undirected graph, and let $T(G)$ be its total graph. The Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.

Is there an example of a graph $G$ such that $\eta(T(G)) > \Delta(G) + 2$ (where $\Delta(G)$ is the maximum degree)?

  • $\begingroup$ Isn't this asking about Hadwiger conjecture for total graphs? en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29 $\endgroup$ – joro May 27 '16 at 12:33
  • 2
    $\begingroup$ It is easy to construct graphs of maximum degree three with arbitrarily large clique minors, so examples are easy to find even without looking at the extra edges in the total graph. $\endgroup$ – Ben Barber May 27 '16 at 16:03

The graph $T(G)$ contains as a subgraph $L(G)$, the line graph of $G$.

Abrams and I constructed a $K_{9k + 1}$ minor in the graph $L(K_{5k+2})$.

  • $\begingroup$ I found that the The Australasian Journal of Combinatorics butchered their SSL settings with a self-signed certificate. It's safe, just don't give it your Social Security Number. $\endgroup$ – yberman May 27 '16 at 16:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.