pith. sign in

arxiv: 1509.01185 · v1 · pith:6VFEIMVInew · submitted 2015-09-03 · 🧮 math.CO

The extremal function for disconnected minors

classification 🧮 math.CO
keywords graphwoodaboveallowscompconjecturescontainingcycles
0
0 comments X
read the original abstract

For a graph $H$ let $c(H)$ denote the supremum of $|E(G)|/|V(G)|$ taken over all non-null graphs $G$ not containing $H$ as a minor. We show that $$c(H) \leq \frac{|V(H)|+\mathrm{comp}(H)}{2}-1,$$ when $H$ is a union of cycles, verifying conjectures of Reed and Wood, and Harvey and Wood. We derive the above result from a theorem which allows us to find two vertex disjoint subgraphs with prescribed densities in a sufficiently dense graph, which might be of independent interest.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.