Small Minors in Dense Graphs

Details Small Minors in Dense Graphs Small Minors in Dense Graphs

2010-05-06

arxiv.org/abs/1005.0895v4

Mathematics

Combinatorics

Scientific paper

A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)\cdot\log n$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)\leq 2^{t-1}+\eps$. For $t\leq 4$, we determine the least value of $f(t)$; in particular $f(3)=2+\eps$ and $f(4)=4+\eps$. For $t\leq4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).

Affiliated with

Also associated with

No associations

Rating

Small Minors in Dense Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small Minors in Dense Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Minors in Dense Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25656