An optimal chromatic bound for the class of \P₃∪ 2K₁,P₃∪ 2K₁\-free graphs

2023/11/09 by Prashant, Athmakoori, Raj, S. Francis
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2311.05231

Abstract

In 1987, A. Gyárfás in his paper ``Problems from the world surrounding perfect graphs'' posed the problem of determining the smallest χ-binding function for G(F,F), when G(F) is χ-bounded. So far the problem has been attempted for only forest F with four or five vertices. In this paper, we address the case when F=P₃∪ 2K₁ and show that if G is a \P₃∪ 2K₁,P₃∪ 2K₁\-free graph with ω(G)≠ 3, then it admits ω(G)+1 as a χ-binding function. Moreover, we also construct examples to show that this bound is tight for all values of ω≠ 3.

Related

• An optimal chromatic bound for (P₂+P₃, gem)-free graphs
• χ-binding functions for some classes of (P₃∪ P₂)-free graphs
• Optimal chromatic bound for (P₂∪ P₄, HVN)-free graphs
• The optimal χ-bound for (P₇,C₄,C₅)-free graphs
• Chromatic bounds for some classes of 2K₂-free graphs