1
$\begingroup$

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)?

Improve this question
$\endgroup$
2
  • $\begingroup$ Isn't this asking about Hadwiger conjecture for total graphs? en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29 $\endgroup$
    – joro
    Commented May 27, 2016 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
    Commented May 27, 2016 at 16:03

1 Answer 1

Reset to default
2
$\begingroup$

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})$.

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 27, 2016 at 16:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .