تقرير
On graphs with no induced $P_5$ or $K_5-e$
| العنوان: | On graphs with no induced $P_5$ or $K_5-e$ |
|---|---|
| المؤلفون: | Char, Arnab, Karthick, T. |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| الوصف: | In this paper, we are interested in some problems related to chromatic number and clique number for the class of $(P_5,K_5-e)$-free graphs, and prove the following. $(a)$ If $G$ is a connected ($P_5,K_5-e$)-free graph with $\omega(G)\geq 7$, then either $G$ is the complement of a bipartite graph or $G$ has a clique cut-set. Moreover, there is a connected ($P_5,K_5-e$)-free imperfect graph $H$ with $\omega(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 ($P_5,K_5-e$)-free graph with $\omega(G)\geq 4$, then $\chi(G)\leq \max\{7, \omega(G)\}$. Moreover, the bound is tight when $\omega(G)\notin \{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 $P_5$-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 ($P_5,K_5-e$)-free graphs which may be independent interest. Comment: This paper is dedicated to the memory of Professor Frederic Maffray on his death anniversary |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2308.08166 |
| رقم الأكسشن: | edsarx.2308.08166 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |