On Graphs With No Induced P5 or K5−e
Arnab Char, T. Karthick · Journal of Graph Theory · 2025
ABSTRACT In this paper, we are interested in some problems related to chromatic number and clique number for the class of ‐free graphs and prove the following the results: (a) If is a connected ()‐free graph with , then either is the complement of a bipartite graph or has a clique cut‐set. Moreover, there is a connected ()‐free imperfect graph with and has no clique cut‐set. This strengthens a result of Malyshev and Lobanova (Discrete Applied Mathematics 219 [2017] 158–166). (b) If is a ()‐free graph with , then . Moreover, the bound is tight when . This result, together with known results, partially answers a question of Ju and Huang (Theoretical Computer Science 993 [2024] Article No.: 114465) and also improves a result of Xu [Manuscript 2022]. While Chromatic Number is known to be ‐hard for the class of ‐free graphs, our results, together with some known results, imply that Chromatic Number can be solved in polynomial time for the class of ()‐free graphs, which may be of independent interest.