Linear χ-binding functions for some classes of (P3∪P2)-free graphs

Abstract

The class of [Formula: see text]-free graphs has been well studied in the past. In the paper “On the chromatic number of [Formula: see text]-free graphs, Discrete Applied Mathematics, 253 (2019), 14–24”, it was shown that the class of [Formula: see text]-free graphs and [Formula: see text]-free graphs admit a linear χ-binding function. In this paper, we study some subclasses of [Formula: see text]-free graphs which is a superclass of [Formula: see text]-free graphs. We show that [Formula: see text]-free graphs and [Formula: see text]-free graphs also admit linear χ-binding functions. In addition, we give a tight χ-binding function for [Formula: see text]-free graphs and improve the χ-bound for [Formula: see text]-free graphs with ω = 4.

Keywords

• Chromatic number
• χ-binding function
• -free graphs and Perfect graphs
• 05C15
• 05C75