Information Technology Reference
In-Depth Information
G
has a proper
k
-coloring, denoted by
ˇ
(
G
). A
proper k-clique-coloring
of a
graph
G
is a
k
-coloring of
G
such that no maximal clique of
G
with size at
least two is monochromatic. A graph
G
is
k-clique-colorable
if
G
has a proper
k
-clique-coloring. The
clique-chromatic number
of
G
is the smallest
k
such that
G
has a proper
k
-clique-coloring, denoted by
ˇ
c
(
G
). Note that
ˇ
c
(
G
)=1if
and only if
G
is an edgeless graph. Since any proper
k
-coloring of
G
is a proper
k
-clique-coloring of
G
,
ˇ
c
(
G
)
ˇ
(
G
). Recall that a
triangle
is the complete
graph
K
3
.If
G
is a triangle-free graph, then maximal cliques of
G
are edges; so
ˇ
c
(
G
)=
ˇ
(
G
). Mycielski [
8
] showed that the family of triangle-free graphs has no
bounded chromatic number. Consequently, it has no bounded clique-chromatic
number, either. On the other hand, many families of graphs have bounded clique-
chromatic numbers, for example, comparability graphs, cocomparability graphs,
and the
k
-power of cycles (see [
2
,
4
,
5
]). In 2004, Bacso et al. [
1
] proved that
almost all perfect graphs are 3-clique-colorable and conjectured that all perfect
graphs are 3-clique-colorable.
A subgraph
H
of a graph
G
is said to be
induced
if, for any pair of vertices
x
and
y
of
H
,
xy
is an edge of
H
if and only if
xy
is an edge of
G
.Fora
given graph
F
,agraph
G
is
F-free
if it does not contain
F
as an induced
subgraph. A graph
G
is (
F
1
,F
2
,...,F
k
)
-free
if it is
F
i
-free for all 1
≤
k
.
In [
6
], Gravier, Hoang and Maffray gave a significant result that, for any graph
F
, the family of all
F
-free graphs has a bounded clique-chromatic number if
and only if
F
is a vertex-disjoint union of paths. Many authors explored more
results in (
F
1
,F
2
,...,F
k
)-free graphs. Gravier and Skrekovski [
7
] in 2003 proved
that (
P
3
+
P
1
)-free graphs unless it is
C
5
, and (
P
5
,C
5
)-free graphs are 2-clique-
colorable. In 2004, Bacso et al. [
1
] showed that (claw, odd hole)-free graphs
are 2-clique-colorable. Later, Defossez [
3
] in 2006 proved that (diamond, odd
hole)-free graphs are 4-clique-colorable, and (bull, odd hole)-free graphs are 2-
clique-colorable.
Given a graph
F
,let
f
(
F
) = max
≤
i
≤
. When
F
1
is an induced subgraph of
F
2
, if a graph
G
is
F
1
-free then
G
is also
F
2
-free, it
follows that
f
(
F
1
)
{
ˇ
c
(
G
)
|
G
is an
F
-free graph
}
≤
f
(
F
2
). In 2003, Gravier, Hoang and Maffray [
6
] showed the
following result.
Theorem 1
Let F be a graph. Then
f
(
F
)
exists if and only if
F
is a vertex-
disjoint union of paths. Moreover,
-if
[
6
]
.
|
V
(
F
)
|≤
2
or F =
P
3
then
f
(
F
)
≤
2
,
-else
f
(
F
)
≤
cc
(
F
)+
|
V
(
F
)
|−
3
where
cc
(
F
)
is the number of connected com-
ponents of a graph
F
.
Furthermore, they proved that (
P
2
+2
P
1
)-free graphs and (
P
3
+2
P
1
)-free
graphs are 3-clique-colorable. Since the cycle
C
5
is both (
P
2
+2
P
1
)-free and
(
P
3
+2
P
1
)-free with
ˇ
c
(
C
5
) = 3, this bound is sharp.
2 Main Results
An
independent set
in a graph is a set of pairwise nonadjacent vertices. A
maxi-
mum independent set
of a graph
G
is a largest independent set of
G
and its size
Search WWH ::
Custom Search