Small K5K_5-models at average degree greater than six

Let GG be a graph, let G|G| denote its number of vertices, and let a K5K_5-model be a model of the complete graph K5K_5 in GG. For a real number ε>0\varepsilon>0, suppose that the average degree of GG is at least 6+ε6+\varepsilon. Small K5K_5-model conjecture. There is a function hh such that every such graph GG contains a K5K_5-model with at most

h(ε)logGh(\varepsilon)\cdot\log|G|

vertices. The conjecture would improve the paper's bound from average degree at least 16+ε16+\varepsilon to the threshold 6+ε6+\varepsilon; the case t=5t=5 is identified as open, while the threshold 66 for forcing a K5K_5-minor follows from Wagner's characterization of graphs with no K5K_5-minor.

Sources & referencesView supporting material

Primary source

Samuel Fiorini, Gwenaël Joret, Dirk Oliver Theis and David R. Wood, “Small Minors in Dense Graphs”, arXiv:1005.0895 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.