Information Technology Reference
In-Depth Information
More Results on Clique-chromatic Numbers
of Graphs with No Long Path
B
Tanawat Wichianpaisarn and Chariya Uiyyasathian
(
)
Faculty of Science, Department of Mathematics and Computer Science,
Chulalongkorn University, Payathai Rd., Bangkok 10330, Thailand
tanawat.wp@gmail.com, chariya.u@chula.ac.th
Abstract.
The clique-chromatic number of a graph is the least number
of colors on the vertices of the graph so that no maximal clique of size at
least two is monochromatic. In 2003, Gravier, Hoang, and Maffray have
shown that, for any graph
F
, the class of
F
-free graphs has a bounded
clique-chromatic number if and only if
F
is a vertex-disjoint union of
paths, and they give an upper bound for all such cases. In this paper,
their bounds for
F
=
P
2
+
kP
1
and
F
=
P
3
+
kP
1
with
k ≥
3are
significantly reduced to
k
+ 1 and
k
+ 2 respectively, and sharp bounds
are given for some subclasses.
·
Keywords:
Clique-chromatic number
Clique-coloring
2010 Mathematics Subject Classification:
05C15
1
Introduction
All graphs considered in this paper are simple. We use terminologies from West's
textbook [
9
].
V
(
G
)and
E
(
G
) denote the vertex set and the edge set of a graph
G
, respectively. The symbols
K
n
,
P
n
and
C
n
denote the complete graph, path,
and cycle, with
n
vertices, respectively. The
diamond
is the complete graph
K
4
minus an edge. The
neighborhood
of a vertex
x
in a graph
G
is the set of vertices
adjacent to
x
, and is denoted by
N
G
(
x
). For
S
V
(
G
),
N
S
(
x
) stands for the
neighborhood of a vertex
x
in
S
,thatis,
N
S
(
x
)=
N
G
(
x
)
ↆ
S
. Given graphs
G
1
,G
2
,...,G
k
with pairwise disjoint vertex sets, the
disjoint union
of graphs
∩
G
1
,G
2
,...,G
k
is the graph with vertex set
i
=1
V
(
G
i
) and edge set
i
=1
E
(
G
i
),
denoted by
G
1
+
G
2
+
···
+
G
k
.For
k
∈
N
,
kG
is the disjoint union of
k
pairwise
disjoint copies of a graph
G
.
A subset
Q
of
V
(
G
)isa
clique
of
G
if any two vertices of
Q
are adjacent.
A clique is
maximal
if it is not properly contained in another clique. A
k-coloring
of a graph
G
is a function
f
:
V
(
G
)
.A
proper k-coloring
of a
graph
G
is a
k
-coloring of
G
such that adjacent vertices have different colors.
The
chromatic number
of a graph
G
is the smallest positive integer
k
such that
ₒ{
1
,
2
,...,k
}
Tanawat Wichianpaisarn—Partially supported by His Royal Highness Crown Prince
Maha Vajiralongkorn Fund.
Search WWH ::
Custom Search