A tight linear bound to the chromatic number of (P₅, K₁+(K₁\cup K₃))-free graphs

Abstract: Let

F_{1}

and

F_{2}

be two disjoint graphs. The union

F_{1} c u p F_{2}

is a 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 the join

F_{1} + F_{2}

is a 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 present a characterization to

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

-free graphs, prove that

c h i (G) l e 2 o m e g a (G) - 1

if

G

is

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

-free. Based on this result, we further prove that

c h i (G) l e

max

2 o m e g a (G), 15

if

G

is a

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

-free graph, and construct an infinite family of

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

-free graphs such that every graph

G

in the family satisfies

c h i (G) = 2 o m e g a (G)

.

This page was built for publication: A tight linear bound to the chromatic number of $(P_5, K_1+(K_1\cup K_3))$-free graphs