Information Technology Reference
In-Depth Information
subset of size larger than 5
n/
6. Note that 14
/
17
≈
5
/
6
−
0
.
01, and thus our
results are almost tight.
Lemma 2.
Let T be a tree on n vertices rooted at any vertex r
(
T
)
.Letc
i
be the
number of vertices with exactly i children. Then c
0
=(
n
+1+
n−
1
i
=1
(
i
−
2)
c
i
)
/
2
.
Proof.
The number of edges in
T
is
n
−
1 and also equals the degree sum divided
by two. Thus,
n−
1
1
.
Since
n−
1
i
=0
c
i
(
i
+1)= 2(
n
−
1) + 1 = 2
n
−
i
=0
c
i
=
n
,
n−
1
i
=0
c
i
(
i
−
n−
1
−
2) + 3
n
=2
n
−
1
,
and
−
2
c
0
=
−
n
−
i
=1
c
i
(
i
−
2)
.
The lemma
1
follows.
Theorem 1.
AtreeT on n vertices contains a column planar set of size at least
14
n/
17
.
Proof.
Root
T
at an arbitrary non-leaf vertex
r
(
T
). Orient every edge towards
the root and topologically sort
T
to obtain an order
v
1
,...,v
n
. We will greedily
add vertices to
R
in this order. More precisely, let
R
0
=
∅
and let
R
i
:=
R
i−
1
∪
{
satisfies Lemma 1 and let
R
i
:=
R
i−
1
otherwise. Let
R
=
R
n
be our final subset of
T
.
We say that a vertex is
marked
if it is in
R
.Consideravertex
v
=
v
i
∈
v
i
}
if
R
i−
1
∪{
v
i
}
R
.
The reason that
v
is not in
R
is that
R
i−
1
∪{
v
}
does not satisfy the condition
inLemma1for
v
or a child
u
of
v
(or both). More precisely,
v
is contained in
exactly one of the following sets:
C
R
(
v
)
X
a
=
{
v
∈
T
\
R
:
|
|
>
2
}
X
b
=
{
v
∈
T
\
R
\
X
a
:
|
C
R
(
v
)
|
>
4
}
|C
R
(
u
)
| >
1
}
X
c
=
{v ∈ T \ R \ X
a
\ X
b
:
X
d
=
{
v
∈
T
\
R
\
X
a
\
X
b
\
X
c
:
|
C
R
(
u
)
|
>
2
}
.
We associate with each such
v
awitnesstree
W
(
v
) as follows (see Fig. 4). If
v
X
a
,thenlet
W
(
v
)be
v
, three vertices of
C
R
(
v
) and a marked child of each
of them (which must exist by definition of
C
R
(
v
)). If
v
∈
∈
X
b
,thenlet
W
(
v
)be
v
and five marked children of
v
.If
v
X
c
,thenlet
W
(
v
)be
v
,
u
, two vertices of
C
R
(
u
) and a marked child of each of them. If
v
∈
∈
X
d
,let
W
(
v
)be
v
,
u
and three
v
v
v
v
u
u
v
∈
X
a
v
∈
X
b
v
∈
X
c
v
∈
X
d
Fig. 4.
The witness tree
W
(
v
)when
v
is in
X
a
,
X
b
,
X
c
or
X
d
. The marked vertices
are black. Dotted line segments indicate that a vertex has at least one child.
