The χ‐Boundedness of (P2 ∪ P3)‐Free Graphs
Wang Xiao, Donghan Zhang · Journal of Mathematics · 2022
In the early 1980s, Gyárfás introduced the concept of the χ‐bound with χ‐binding functions thereby extending the notion of perfectness. There are a number of challenging conjectures about the χ‐bound. Let χ(G), ω(G), and Δ(G) be the chromatic number, clique number, and maximum degree of a graph G, respectively. In this paper, we prove that if G is a triangle‐free and (P2 ∪ P3)‐free graph, then χ(G) ≤ 3 unless G is one of eight graphs with Δ(G) = 5 and χ(G) = 4, where the eight graphs are extended from the Grötzsch graph as a Mycielskian of a 5‐cycle graph. Moreover, we also show that χ(G) ≤ 3ω(G) if G is a {P2 ∪ P3, W4}‐free graph.