Optimal chromatic bound for (P₂+P₃, P₂+ P₃)-free graphs

2022/05/16 by Char, Arnab, Karthick, T.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2205.07447

Abstract

For a graph G, let χ(G) (ω(G)) denote its chromatic (clique) number. A P₂+P₃ is the graph obtained by taking the disjoint union of a two-vertex path P₂ and a three-vertex path P₃. A P₂+P₃ is the complement graph of a P₂+P₃. In this paper, we study the class of (P₂+P₃, P₂+P₃)-free graphs and show that every such graph G with ω(G)≥ 3 satisfies χ(G)≤ max \ω(G)+3, \lfloor(3)/(2) ω(G) \rfloor-1 \. Moreover, the bound is tight. Indeed, for any k∈ \mathbb N and k≥ 3, there is a (P₂+P₃, P₂+P₃)-free graph G such that ω(G)=k and χ(G)=max\k+3, \lfloor(3)/(2) k \rfloor-1 \.

Related

• A tight linear bound to the chromatic number of (P₅, K₁+(K₁∪ K₃))-free graphs
• Tight Chromatic Upper Bound for 3 Times K1, 2 Times K1 + (K2 UNION K1)-free Graphs
• Optimal chromatic bound for (P₃∪ P₂, house)-free graphs
• An optimal chromatic bound for (P₂+P₃, gem)-free graphs
• Improved chromatic bounds for (P₂∪ P₃)-free graphs