论文标题
$（2p_4，c_5）$ - 免费图形
On 3-Coloring of $(2P_4,C_5)$-Free Graphs
论文作者
论文摘要
在过去的十年中，遗传图的三色一直是一个深入研究的问题。遗传图类的特征是（可能是无限的）最小禁止诱导子图$ H_1，H_2，\ ldots $;同类中的图称为$（H_1，H_2，\ ldots）$ - 免费。 3色的复杂性远非被理解，即使是由几个小型禁止的诱导子图定义的类也是如此。对于$ h $ fre的图形，最多七个顶点的任何$ h $都可以解决任何复杂性。八个顶点只有两个未解决的案例，即$ 2p_4 $和$ p_8 $。对于$ p_8 $ free图，一些部分结果是已知的，但据我们所知，尚未探索$ 2p_4 $ free图。在本文中，我们表明3色问题是可在$（2P_4，C_5）$ - 免费图表上溶解的多项式时间。
The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs $H_1,H_2,\ldots$; the graphs in the class are called $(H_1,H_2,\ldots)$-free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For $H$-free graphs, the complexity is settled for any $H$ on up to seven vertices. There are only two unsolved cases on eight vertices, namely $2P_4$ and $P_8$. For $P_8$-free graphs, some partial results are known, but to the best of our knowledge, $2P_4$-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on $(2P_4,C_5)$-free graphs.
