2024/05/28 by Char, Arnab, Karthick, T.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.17819
Given a graph G, the parameters χ(G) and ω(G) respectively denote the chromatic number and the clique number of G. A function f : ℕ → ℕ such that f(1) = 1 and f(x) ≥ x, for all x ∈ ℕ is called a χ-binding function for the given class of graphs \calG if every G ∈ \calG satisfies χ(G) ≤ f(ω(G)), and the smallest χ-binding function f^* for \calG is defined as f^*(x) := max\χ(G)| G∈ \cal G and ω(G)=x\. In general, the problem of obtaining the smallest χ-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of (P2+ P3, gem)-free graphs, and prove that the function ϕ:ℕ→ ℕ defined by ϕ(1)=1, ϕ(2)=4, ϕ(3)=6 and ϕ(x)=\lceil(1)/(4)(5x-1)\rceil, for x≥ 4 is the smallest χ-binding function for the class of (P2+ P3, gem)-free graphs.