Information Technology Reference
In-Depth Information
S, X
i
where 1
≤
i
≤
ʱ
(
G
), and
Y
R
where
R
ↆ
S
and
|
R
|
=
ʱ
(
G
)
−
1. Let
f
be
the coloring of
G
defined by
⊧
⊨
1
,
if
v
∈
S
∈
α
(
G
)
i
=1
f
(
v
)=
2
,
if
v
X
i
⊩
min(
R
)+2
,
if
v
∈
Y
R
where
R
=
S
\
N
S
(
v
)
.
Let
R
ↆ
S
where
Y
R
=
∅
, and let
y
∈
Y
R
.If
R
=
S
, then
N
S
(
y
)=
∅
;so
S
∪{
y
}
is an independent set of
G
, a contradiction. If
k
≤|
R
|≤
ʱ
(
G
)
−
2, then
the subgraph of
G
induced by
S
∪{
y
}
contains an induced subgraph
P
3
+
kP
1
,
a contradiction. Thus
k
. Hence
f
is a
(
k
+ 2)-coloring of
G
. Now, suppose that
G
has a monocolored maximal clique
Q
of size at least two, say colored by
m
. Since
S
is an independent set,
m
|
R
|≤
k
−
1, and it follows that min(
R
)
≤
=1.
If
m
= 2, then
Q
X
i
for some
i
. We have that
s
i
is adjacent to all vertices of
Q
, a contradiction. Now, assume
m
ↆ
3. Since
s
min(
R
)
is adjacent to all vertices
of
Y
R
,
s
m−
2
is adjacent to all vertices of
Q
, a contradiction. Thus
f
is a proper
(
k
+ 2)-clique-coloring of
G
, and hence
ˇ
c
(
G
)
≥
≤
k
+2.
Theorem
3
ensures that every (
P
2
+
kP
1
)-free graph where
k
3is(
k
+1)-clique-
colorable but we have found no graph guaranteeing this sharpness yet. However,
when
k
=3and4,thereisa(
P
2
+
kP
1
)-free graph which is
k
-clique-colorable,
namely, the cycle
C
5
is (
P
2
+3
P
1
)-free and
ˇ
c
(
C
5
) = 3, and the 4-chromatic
Mycielski's graph
G
4
[
8
]is(
P
2
+4
P
1
)-free and
ˇ
c
(
G
4
) = 4. (See Fig.
1
) Notice
that both of them are diamond-free, this suggests the result in Theorem
5
.
≥
Fig. 1.
The 4-chromatic Mycielski's graph
G
4
Theorem 5.
For
k
≥
3
,a
(
P
2
+
kP
1
,diamond
)
-free graph is
k
-clique-colorable.
Proof.
Let
G
be a (
P
2
+
kP
1
, diamond)-free graph. If
ʱ
(
G
)
≤
k
, then
ˇ
c
(
G
)
≤
k
by Theorem
2
. Assume
ʱ
(
G
)
k
+1. Use the same terminologies and arguments
as in the proof of Theorem
3
, we can define a
k
-coloring of
G
as follows:
≥
Search WWH ::
Custom Search