Linear \chi-binding functions for \{P₃\cup P₂, gem\}-free graphs

Abstract: Finding families that admit a linear

c h i

-binding function is a problem that has interested researchers for a long time. Recently, the question of finding linear subfamilies of

2 K_{2}

-free graphs has garnered much attention. In this paper, we are interested in finding a linear subfamily of a specific superclass of

2 K_{2}

-free graphs, namely

(P_{3} c u p P_{2})

-free graphs. We show that the class of

P_{3} c u p P_{2}, g e m

-free graphs admits

f = 2 o m e g a

as a linear

c h i

-binding function. Furthermore, we give examples to show that the optimal

c h i

-binding function

f^{*} g e q l e f t l c e i l f r a c 5 o m e g a (G) 4 i g h t c e i l

for the class of

P_{3} c u p P_{2}, g e m

-free graphs and that the

c h i

-binding function

f = 2 o m e g a

is tight when

o m e g a = 2

and

3

.

This page was built for publication: Linear $\chi$-binding functions for $\{P_3\cup P_2, gem\}$-free graphs