2023/08/16 by Arnab Char, Char, Arnab, T. Karthick +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2308.08166
openalex publication_date 2023/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we are interested in some problems related to chromatic number and clique number for the class of (P5,K5-e)-free graphs, and prove the following. (a) If G is a connected (P5,K5-e)-free graph with ω(G)≥ 7, then either G is the complement of a bipartite graph or G has a clique cut-set. Moreover, there is a connected (P5,K5-e)-free imperfect graph H with ω(H)=6 and has no clique cut-set. This strengthens a result of Malyshev and Lobanova [Disc. Appl. Math. 219 (2017) 158--166]. (b) If G is a (P5,K5-e)-free graph with ω(G)≥ 4, then χ(G)≤ max\7, ω(G)\. Moreover, the bound is tight when ω(G)∉ \4,5,6\. This result together with known results partially answers a question of Ju and Huang [arXiv:2303.18003 [math.CO] 2023], and also improves a result of Xu [Manuscript 2022]. While the "Chromatic Number Problem" is known to be NP-hard for the class of P5-free graphs, our results together with some known results imply that the "Chromatic Number Problem" can be solved in polynomial time for the class of (P5,K5-e)-free graphs which may be independent interest.