Optimal chromatic bound for (P2+P3,P2+P3¯ {P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}})‐free graphs

Abstract: For a graph

G

, let

c h i (G)

(

o m e g a (G)

) denote its chromatic (clique) number. A

P_{2} + P_{3}

is the graph obtained by taking the disjoint union of a two-vertex path

P_{2}

and a three-vertex path

P_{3}

. A

is the complement graph of a

P_{2} + P_{3}

. In this paper, we study the class of (

P_{2} + P_{3}

,

)-free graphs and show that every such graph

G

with

o m e g a (G) g e q 3

satisfies

c h i (G) l e q m a x o m e g a (G) + 3, l f l o o r f r a c 32 o m e g a (G) f l o o r - 1

. Moreover, the bound is tight. Indeed, for any

k i n m a t h b b N

and

k g e q 3

, there is a (

P_{2} + P_{3}

,

)-free graph

G

such that

o m e g a (G) = k

and

c h i (G) = m a x k + 3, l f l o o r f r a c 32 k f l o o r - 1

.

Recommendations

Cites Work

This page was built for publication: Optimal chromatic bound for (P2+P3,P2+P3¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs