 322 pág.

Graph Theory

DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
Pré-visualização50 páginas
in Sparse Graphs
For every H 2H, any graph obtained from H by one of the following
three operations will again be in H:
(i) deletion of an edge, if kHk > m jHj+ f(jHj)¡ ¡m2 ¢+ 1;
(ii) deletion of a vertex of degree at most 76m;
(iii) contraction of an edge xy 2 H such that x and y have at most
7
6m¡ 1 common neighbours in H.
Starting with G1, let us apply these operations as often as possible, and
let H0 2 H be the graph obtained eventually. SinceH0
kKmk = m jKmj ¡m¡ ¡m2 ¢
and
f(m) = ¡ 56m > ¡m;
Km does not have enough edges to be in H; thus, H contains no graph
on m vertices. Hence jH0j > m, and in particular H0 6= ;. Let x1 2 H0x1
be a vertex of minimum degree, and put
H1 := H0 [ fx1 g[NH0(x1) ] :H1
We shall prove that the minimum degree of H := H1 is as large as
claimed in the lemma.
Note flrst that
\u2013(H1) > 76m: (3)
Indeed, since H0 is minimal with respect to (ii) and (iii), we have d(x1) >
7
6m in H0 (and hence in H1), and every vertex y 6= x1 of H1 has more
than 76m ¡ 1 common neighbours with x1 (and hence more than 76m
neighbours in H1 altogether). In order to convert (3) into the desired
inequality of the form
2\u2013(H1) > jH1j+fim ;
we need an upper bound for jH1j in terms of m. Since H0 lies in H but
is minimal with respect to (i), we have
kH0k < m jH0j+
\u2021
1
6m jH0j ¡ 16m2¡ 56m
·
¡ ¡m2 ¢+ 1
= 76m jH0j ¡ 46m2¡ 13m+ 1
6
(2)
7
6m jH0j ¡ 46m2: (4)
8.1 Topological minors 177
By the choice of x1 and deflnition of H1, therefore,
jH1j ¡ 1 = \u2013(H0)
6 2 &quot;(H0)
<
(4)
7
3m¡ 43m2=jH0j
6
(1)
7
3m¡ 13m
= 2m;
so jH1j 6 2m. Hence,
2\u2013(H1) >
(3)
2m+ 13m
> jH1j+ 13m
>
(2)
jH1j+ 16k
as claimed. \u2044
Proof of Theorem 8.1.1. We prove the assertion for c := 1116. Let (1.4.2)
G be a graph with d(G) > 1116r2. By Theorem 1.4.2, G has a subgraph
G0 such that G0
\u2022(G0) > 279r2 > 276r2 + 3r :
Pick a set X := fx1; : : : ; x3r g of 3r vertices in G0, and let G1 := G0¡X. X
For each i = 1; : : : ; 3r choose a set Yi of 5r neighbours of xi in G1; let G1; Yi
these sets Yi be disjoint for difierent i. (This is possible since \u2013(G0) >
\u2022(G0) > 15r2 + jXj.)
As
\u2013(G1) > \u2022(G1) > \u2022(G0)¡ jXj > 276r2;
we have &quot;(G1) > 138r2. By Lemma 8.1.3, G1 has a minor H with
2\u2013(H) > jHj+ 23r2 and is therefore (15r2; 7r2)-linked by Lemma 8.1.2;
let Z µ S3ri=1 Yi be a set of 7r2 vertices that is linked in G1. Z
For all i = 1; : : : ; 3r let Zi := Z \ Yi. Since Z is linked, it su\u2013ces Zi
to flnd r indices i with jZij > r¡ 1: then the corresponding xi will be
the branch vertices of a TKr in G0. If r such i cannot be found, then
jZij 6 r¡ 2 for all but at most r¡ 1 indices i. But then
jZj =
3rX
i=1
jZij 6 (r¡ 1) 5r+ (2r+ 1)(r¡ 2) < 7r2 = jZj ;
178 8. Substructures in Sparse Graphs
Although Theorem 8.1.1 already gives a good estimate, it seems
very di\u2013cult to determine the exact average degree needed to force a
TKr subgraph, even for small r. We shall come back to the case of
r = 5 in Section 8.3; more results and conjectures are given in the notes.
The following almost counter-intuitive result of Mader implies that
the existence of a topological Kr minor can be forced essentially by large
girth. In the next section, we shall prove the analogue of this for ordinary
minors.
Theorem 8.1.4. (Mader 1997)
For every graph H of maximum degree d > 3 there exists an integer k
such that every graph G of minimum degree at least d and girth at least k
contains H as a topological minor.
As discussed already in Chapter 5.2 and the introduction to Chap-
ter 7, no constant average degree, however large, will force an arbitrary
graph to contain a given graph H as a subgraph|as long as H contains
at least one cycle. By Proposition 1.2.2 and Corollary 1.5.4, on the other
hand, any graph G contains all trees on up to &quot;(G) + 2 vertices. Large
average degree therefore does ensure the occurrence of any flxed tree T
as a subgraph. What can we say, however, if we would like T to occur
as an induced subgraph?
Here, a large average degree appears to do as much harm as good,
even for graphs of bounded clique number. (Consider, for example,
complete bipartite graphs.) It is all the more remarkable, then, that
the assumption of a large chromatic number rather than a large average
degree seems to make a difierence here: according to a conjecture of
Gy¶arf¶as, any graph of large enough chromatic number contains either a
large complete graph or any given tree as an induced subgraph. (For-
mally: for every integer r and every tree T , there exists an integer k such
that every graph G with ´(G) > k and !(G) < r contains an induced
copy of T .)
The weaker topological version of this is indeed true:
Theorem 8.1.5. (Scott 1997)
For every integer r and every tree T there exists an integer k such that
every graph with ´(G) > k and !(G) < r contains an induced copy of
some subdivision of T .
8.2 Minors 179
8.2 Minors
According to Theorem 8.1.1, an average degree of cr2 su\u2013ces to force the
existence of a topological Kr minor in a given graph. If we are content
with any minor, topological or not, an even smaller average degree will
do: in a pioneering paper of 1968, Mader proved that every graph with an
average degree of at least cr log r has a Kr minor. The following result,
the analogue to Theorems 7.1.1 and 8.1.1 for general minors, determines
the precise average degree needed as a function of r, up to a constant c:
Theorem 8.2.1. (Kostochka 1982; Thomason 1984)
There exists a c 2 R such that, for every r 2 N, every graph G of average
degree d(G) > c r
p
log r has a Kr minor. Up to the value of c, this
bound is best possible as a function of r.
The easier implication of the theorem, the fact that in general an average
degree of c r
p
log r is needed to force a Kr minor, follows from consider-
ing random graphs, to be introduced in Chapter 11. The converse impli-
cation, the fact that this average degree su\u2013ces, is proved by methods
similar to those described in Section 8.1.
Rather than proving Theorem 8.2.1, we therefore devote the remain-
der of this section to another striking result on forcing minors. At flrst
glance, this result is so surprising that it seems almost paradoxical: as
long as we do not merely subdivide edges, we can force a Kr minor in a
graph simply by raising its girth (Corollary 8.2.3)!
Theorem 8.2.2. (Thomassen 1983)
Given an integer k, every graph G with girth g(G) > 4k¡3 and \u2013(G) > 3
has a minor H with \u2013(H) > k.
Proof . As \u2013(G) > 3, every component of G contains a cycle. In particu- (1.5.3)
lar, the assertion is trivial for k 6 2; so let k > 3. Consider the vertex
set V of a component of G, together with a partition fV1; : : : ; Vm g of V; Vi
V into as many connected sets Vi with at least 2k¡ 2 vertices each as m
possible. (Such a partition exists, since jV j > g(G) > 2k¡ 2 and V is
connected in G.)
We flrst show that every G [Vi ] is a tree. To this end, let Ti be a
spanning tree of G [Vi ]. If G [Vi ] has an edge e =2 Ti, then Ti+e contains
a cycle C; by assumption, C has length at least 4k¡3. The edge (about)
opposite e on C therefore separates the path C ¡ e, and hence also Ti,
into two components with at least 2k¡ 2 vertices each. Together with
the sets Vj for j 6= i, these two components form a partition of V into
m+ 1 sets that contradicts the maximality of m.
So each G [Vi ] is indeed a tree, i.e. G [Vi ] = Ti. As \u2013(G) > 3, the Ti
degrees in G of the vertices in Vi sum to at least 3 jVij, while the edges
of Ti account for only 2 jVij ¡ 2 in this sum. Hence for each i, G has
180 8. Substructures in Sparse Graphs
at least jVij+ 2 > 2k edges joining Vi to V r Vi. We shall prove that
every Vi sends at most two edges to each of the other Vj ; then Vi must
send edges to at least k of those Vj , so the Vi are the branch sets of an
MH µ G with \u2013(H) >