On the chromatic number of some P₅-free graphs

Abstract: Let

G

be a graph. We say that

G

is perfectly divisible if for each induced subgraph

H

of

G

,

V (H)

can be partitioned into

A

and

B

such that

H [A]

is perfect and

o m e g a (H [B]) < o m e g a (H)

. We use

P_{t}

and

C_{t}

to denote a path and a cycle on

t

vertices, respectively. For two disjoint graphs

F_{1}

and

F_{2}

, we use

F_{1} c u p F_{2}

to denote the graph with vertex set

V (F_{1}) c u p V (F_{2})

and edge set

E (F_{1}) c u p E (F_{2})

, and use

F_{1} + F_{2}

to denote the graph with vertex set

V (F_{1}) c u p V (F_{2})

and edge set

E (F_{1}) c u p E (F_{2}) c u p x y; |; x i n V (F_{1}) m b o x a n d y i n V (F_{2})

. In this paper, we prove that (i)

(P_{5}, C_{5}, K_{2, 3})

-free graphs are perfectly divisible, (ii)

c h i (G) l e 2 o m e g a^{2} (G) - o m e g a (G) - 3

if

G

is

(P_{5}, K_{2, 3})

-free with

o m e g a (G) g e 2

, (iii)

c h i (G) l e 3 o v e r 2 (o m e g a^{2} (G) - o m e g a (G))

if

G

is

(P_{5}, K_{1} + 2 K_{2})

-free, and (iv)

c h i (G) l e 3 o m e g a (G) + 11

if

G

is

(P_{5}, K_{1} + (K_{1} c u p K_{3}))

-free.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: On the chromatic number of some \(P_5\)-free graphs