Coloring of a superclass of 2K₂-free graphs

Abstract: The class of

2 K_{2}

-free graphs has been well studied in various contexts in the past. In this paper, we study the chromatic number of

b u t t e r f l y, h a m m e r

-free graphs, a superclass of

2 K_{2}

-free graphs and show that a connected

b u t t e r f l y, h a m m e r

-free graph

G

with

o m e g a (G) e q 2

admits

as a

c h i

-binding function which is also the best available

c h i

-binding function for its subclass of

2 K_{2}

-free graphs. In addition, we show that if

H i n C_{4} + K_{p}, P_{4} + K_{p}

, then any

b u t t e r f l y, h a m m e r, H

-free graph

G

with no components of clique size two admits a linear

c h i

-binding function. Furthermore, we also establish that any connected

b u t t e r f l y, h a m m e r, H

-free graph

G

where

H i n (K_{1} c u p K_{2}) + K_{p}, 2 K_{1} + K_{p}

, is perfect for

o m e g a (G) g e q 2 p

.

Cites Work

This page was built for publication: Coloring of a superclass of \(2K_2\)-free graphs