More Results on Clique-chromatic Numbers of Graphs with No Long Path - Discrete and Computational Geometry and Graphs - page 186

is denoted by ʱ ( G ). Bacso et al. [ 1 ] stated the relationship between the clique-
chromatic number and the size of a maximum independent set of a graph, as
follows.

Theorem 2 [ 1 ] . Let G be a graph. If G = C 5 and G is not a complete graph,

then ˇ c ( G ) ≤ ʱ ( G ) .

It follows from Theorem 1 that every ( P 2 + kP 1 )-free graph is (2 k )-clique-
colorable and every ( P 3 + kP 1 )-free graph is (2 k +1)-clique-colorable. We improve
these upper bounds for k

≥ 3.

Theorem 3. For k ≥ 3 ,a ( P 2 + kP 1 ) -free graph is ( k +1) -clique-colorable.

Proof. Let G be a ( P 2 + kP 1 )-free graph. Let S = { s 0 ,s 1 ,...,s α ( G ) − 1 } be a

maximum independent set of G .If ʱ ( G ) ≤ k , then ˇ c ( G ) ≤ k by Theorem 2 .

Assume ʱ ( G ) ≥ k +1. Let M ( s 0 )= V ( G ) \ ( S ∪ N G ( s 0 )). For R ↆ S \{ s 0 } ,

define Y R = { v ∈ M ( s 0 ) | N S ( v )= S \ ( { s 0 }∪ R ) } and min( R ) = min { i ∈

N | s i / ∈ R } . In particular, min( ∅ ) = 1. Note that V ( G ) is the disjoint union of

S, N G ( s 0 )and Y R where R ↆ S \{ s 0 } .Let f be the coloring of G defined by

⊧
⊨

1 , if v ∈ S

f ( v )=

2 , if v

∈ N G ( s 0 )

⊩

min( R )+2 , if v ∈ Y R where R = S \ ( { s 0 }∪ N S ( v )) .

Now, let R ↆ S \{ s 0 } where Y R = ∅ , and let y ∈ Y R .If R = S \{ s 0 } , then

N S ( y )= ∅

;so S

∪{ y }

is an independent set of G . This contradicts the maximality

of S .Thus R = S

\{ s 0 } | R |≥ k −

1, then the subgraph of G induced by S

∪{ y }

.If

contains an induced subgraph P 2 + kP 1 , a contradiction. Thus | R |≤ k − 2, and

it follows that min( R ) 1. Therefore, f is a ( k + 1)-coloring of G . 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

≤ k −

. Note that s min( R )
is adjacent to all vertices of Y R .Thus s m− 2 is adjacent to all vertices of Q .
Then Q

=1.Thus Q ∩ S = ∅

∪{ s m− 2 } is a clique of G . It contradicts the maximality of Q . Hence

ˇ c ( G ) ≤ k +1.

Theorem 4. For k ≥ 3 ,a ( P 3 + kP 1 ) -free graph is ( k +2) -clique-colorable.

Proof. Let G be a ( P 3 + kP 1 )-free graph. Let S = { s 1 ,s 2 ,...,s α ( G ) } be a maxi-

mum independent set of G .If ʱ ( G ) ≤ k + 1, then ˇ c ( G ) ≤ k + 1 by Theorem 2 .

Assume ʱ ( G ) ≥ k +2. For 1 ≤ i ≤ ʱ ( G ), let X i = { v ∈ V ( G ) \ S | N S ( v )= { s i }} .

Suppose that there is an edge, say x i x j , between X i and X j where i = j . Then

there exist k vertices in S together with s i ,x i ,x j form an induced sub-

graph P 3 + kP 1 of G , a contradiction. Thus there is no edge between any two X i 's.
For R

\{ s i ,s j }

ↆ S where | R | = ʱ ( G ) − 1, define Y R = { v ∈ V ( G ) \ S | N S ( v )= S \ R }

and min( R ) = min { i ∈ N | s i / ∈ R } . Note that V ( G ) is the disjoint union of