标题： 关于近似最优可着色图 显示英文标题

标题： On near optimal colorable graphs

摘要： 一个图的类$\cal G$被称为\emph{接近最优可着色}，如果存在一个常数$c\in \mathbb{N}$，使得每个图$G\in \cal G$都满足$\chi(G) \leq \max\{c, \omega(G)\}$，其中$\chi(G)$和$\omega(G)$分别表示$G$的色数和团数。 近最优可着色图的类是$\chi$-有界图类的一个重要子类，在文献中得到了广泛研究。 在本文中，我们证明了($F, K_4-e$)-自由图的类是近最优可着色的，其中$F\in \{P_1+2P_2,2P_1+P_3,3P_1+P_2\}$和图$K_4-e$通常被称为{\em 钻石}。 这部分回答了Ju和Huang [理论计算机科学 993 (2024) 文章编号: 114465]提出的一个问题，并与Schiermeyer（未发表）提出的问题有关。 此外，利用这些结果结合一些早期已知的结果，我们还提供了另一种证明，说明对于($F, K_4-e$)-free图类，\textsc{色数}问题可以在多项式时间内求解，其中$F\in \{P_1+2P_2,2P_1+P_3,3P_1+P_2\}$。 显示英文摘要

摘要： A class of graphs $\cal G$ is said to be \emph{near optimal colorable} if there exists a constant $c\in \mathbb{N}$ such that every graph $G\in \cal G$ satisfies $\chi(G) \leq \max\{c, \omega(G)\}$, where $\chi(G)$ and $\omega(G)$ respectively denote the chromatic number and clique number of $G$. The class of near optimal colorable graphs is an important subclass of the class of $\chi$-bounded graphs which is well-studied in the literature. In this paper, we show that the class of ($F, K_4-e$)-free graphs is near optimal colorable, where $F\in \{P_1+2P_2,2P_1+P_3,3P_1+P_2\}$ and the graph $K_4-e$ is commonly referred as the {\em diamond}. This partially answers a question of Ju and Huang [Theoretical Computer Science 993 (2024) Article No.: 114465] and is related to a question of Schiermeyer (unpublished). Furthermore, using these results with some earlier known results, we also provide an alternate proof to the fact that the \textsc{Chromatic Number} problem for the class of ($F, K_4-e$)-free graphs is solvable in polynomial time, where $F\in \{P_1+2P_2,2P_1+P_3,3P_1+P_2\}$.