The Hadwiger number of $L(K_n)$

Question

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows:

• $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b \big\}$;
• $E(L(K_n)) = \big\{\{x,y\}: x,y\in V(L(K_n)) \text{ and } x\cap y \neq \emptyset\big\}$.

For any graph $G=(V,E)$ the Hadwiger number $\eta(G)$ is the largest $n\in \omega$ such that $K_n$ is a minor of $G$.

In this post it is shown that $\eta(L(K_5)) \geq 6$, and it's easy to see that $\eta(L(K_n)) \geq n+1$ for $n\geq 5$.

Question: Given a positive integer $k\in\mathbb{N}$, is there $n\in \mathbb{N}$ such that $\eta(L(K_n)) \geq k\cdot n$?

Answer 1

Claim. For all even $n \geq 4$, $\eta(L(K_n)) \geq \frac{3n-4}{2}$ and for all odd $n \geq 3, \eta(L(K_n)) \geq \frac{3n-3}{2}$

Proof. A clique-minor of size $k$ in $L(K_n)$ corresponds to $k$ edge-disjoint connected subgraphs of $K_n$ which pairwise intersect.

Let $n$ be even. For our $\frac{3n-4}{2}$ subgraphs we first take the $n-1$ edges of a star centered at $x$. By an old theorem of Walecki, the edges of $K_n-x$ can be decomposed into Hamiltonian cycles. There are $\frac{1}{2}(n-2)$ such cycles, giving us $\frac{3n-4}{2}$, as required.

For $n$ odd, we use the same argument but take a Hamiltonian path decomposition of $K_n-x$ instead.

Answer 2

Here is an idea for a yes answer: put $k$ walkers at every vertex. Order the edges randomly, and also randomly pick an orientation on each edge randomly. Now in order, walk the walker across the current edge who has been sitting at the starting vertex the longest (if the vertex has at least one walker). This should give $kn$ edge-disjoint walks of length $\sim \frac{n}{2k}$ which look very similar to random walks, so they should pairwise intersect.