Forcing a 2-regular minor

Importance: Medium ✭✭
Keywords: minors
Recomm. for undergrads: yes
Posted by: David Wood
on: March 16th, 2014

\begin{conjecture} Every graph with average degree at least $\frac{4}{3}t-2$ contains every 2-regular graph on $t$ vertices as a minor. \end{conjecture}

Reed and Wood [RW] explained that a result of Corradi and Hajnal [CH] implies that if $H$ is the graph consisting of $k$ disjoint triangles, then every graph with average degree at least $4k-2$ contains $H$ as a minor. Moreover, the bound of $4k-2$ is best possible since the complete bipartite graph $K_{2k-1,n}$ contains no $H$-minor, but has average degree tending to $4k-2$ (as $n\rightarrow\infty$). Thus the conjecture would generalise this result.

Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

[CH] Keresztely Corradi and Andras Hajnal. On the maximal number of independent circuits of a graph. \emph{Acta Math. Acad. Sci. Hungar.}, 14:423–443, 1963.

*[RW] Bruce Reed and David R. Wood. Forcing a sparse minor, arXiv:\arxiv[1402.0272]{1402.0272}, 2013.


* indicates original appearance(s) of problem.