The reviewed record of science sign in
Pith

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

The extremal function for disconnected minors

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:6VFEIMVIrecord.jsonopen to challenge →

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.