0
$\begingroup$

Does the total graph of a regular finite graph with maximum degree $\Delta$ have a $K_{\Delta+2}$ minor?

I think no. It has a clique of order $\Delta+1$. But, I dont think that deleting a few edges and contracting the vertices could ever produce a clique with an extra vertex. Specifically, since the structure is similar to line graph of the graph, and line graph is not seen to have such a minor, I think even the total graph of a graph does not have a $K_{\Delta+2}$ minor. Any hints? Thanks beforehand.

Improve this question
$\endgroup$
13
  • $\begingroup$ Are the graphs required to be finite? If no, then the infinite path is a counterexample: the total graph of a infinite path is outerplanar, so it does not have any $K_4$ minor. $\endgroup$
    – LeechLattice
    Commented Dec 18, 2019 at 14:15
  • $\begingroup$ @LeechLattice yes, edited the question. By the way, did you mean that the total graph of an infinite path has a $K_4$ minor? Otherwise, it would not be a counterexample, rather, an example in the theorems' favour $\endgroup$
    – vidyarthi
    Commented Dec 18, 2019 at 14:26
  • $\begingroup$ No, because the total graph of an infinite graph is outerplanar. $\endgroup$
    – LeechLattice
    Commented Dec 18, 2019 at 14:28
  • 3
    $\begingroup$ I really wish you would try some small examples before posting your conjectures. (Or at least post them on MSE.) I had never even heard of total graph. I looked it up, and the first example I tried to help me understand was a counter-example. Start with $K_3$, with $\Delta=2$. The total graph of this has six vertices, and is isomorphic to $K_6$ minus a perfect matching. Contract any edge, and you get $K_5$ minus an edge, which contains a $K_4$. $\endgroup$
    – verret
    Commented Dec 18, 2019 at 23:43
  • 1
    $\begingroup$ @vidyarthi Can you explain why you think this is a counterexample to the Hadwiger Conjecture? $\endgroup$
    – verret
    Commented Dec 19, 2019 at 6:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .