Optimal chromatic bound for (P_2+P_3, P̅_̅2̅+̅ ̅P̅_̅3̅)-free graphs
share
For a graph G, let χ(G) (ω(G)) denote its chromatic (clique) number. A P_2+P_3 is the graph obtained by taking the disjoint union of a two-vertex path P_2 and a three-vertex path P_3. A P̅_̅2̅+̅P̅_̅3̅ is the complement graph of a P_2+P_3. In this paper, we study the class of (P_2+P_3, P̅_̅2̅+̅P̅_̅3̅)-free graphs and show that every such graph G with ω(G)≥ 3 satisfies χ(G)≤max{ω(G)+3, ⌊3/2ω(G) ⌋-1 }. Moreover, the bound is tight. Indeed, for any k∈ℕ and k≥ 3, there is a (P_2+P_3, P̅_̅2̅+̅P̅_̅3̅)-free graph G such that ω(G)=k and χ(G)=max{k+3, ⌊3/2 k ⌋-1 }.
READ FULL TEXT