UP - logo
E-resources
Full text
Peer reviewed Open access
  • Optimal chromatic bound for...
    Char, Arnab; Karthick, Thiyagarajan

    Journal of graph theory, February 2024, 2024-02-00, 20240201, Volume: 105, Issue: 2
    Journal Article

    For a graph G $G$, let χ( G ) $\chi (G)$ (ω( G ) $\omega (G)$) denote its chromatic (clique) number. A P 2 + P 3 ${P}_{2}+{P}_{3}$ is the graph obtained by taking the disjoint union of a two‐vertex path P 2 ${P}_{2}$ and a three‐vertex path P 3 ${P}_{3}$. A P 2 + P 3 ¯ $\bar{{P}_{2}+{P}_{3}}$ is the complement graph of a P 2 + P 3 ${P}_{2}+{P}_{3}$. In this paper, we study the class of (P 2 + P 3 , P 2 + P 3 ¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graphs and show that every such graph G $G$ with ω( G ) ≥ 3 $\omega (G)\ge 3$ satisfies χ( G ) ≤ max{ω( G ) + 3 ,⌊3 2 ω( G ) ⌋ − 1 } $\chi (G)\le \max \{\omega (G)+3,\lfloor \phantom{\rule-0.5em{}{0ex}}\frac{3}{2}\omega (G)\rfloor -1\}$. Moreover, the bound is tight. Indeed, for any k ∈ N $k\in {\mathbb{N}}$ and k ≥ 3 $k\ge 3$, there is a (P 2 + P 3 , P 2 + P 3 ¯ ${P}_{2}+{P}_{3},\bar{{P}_{2}+{P}_{3}}$)‐free graph G $G$ with ω( G ) = k $\omega (G)=k$ and χ( G ) = max{k + 3 ,⌊3 2 k ⌋ − 1 } $\chi (G)=\max \{k+3,\lfloor \phantom{\rule-0.5em{}{0ex}}\frac{3}{2}k\rfloor -1\}$.