论文标题
$ k $ - $ p_5 $ - free Graphs中的关键图
$k$-Critical Graphs in $P_5$-Free Graphs
论文作者
论文摘要
给定两个图$ h_1 $和$ h_2 $，图$ g $是$（H_1，H_2）$ - 如果它包含诱导子图同构为$ H_1 $或$ H_2 $，则免费。令$ p_t $为$ t $顶点的路径。如果$ g $具有色度$ k $，则图$ g $是$ k $ - vertex-关键的，但是每个适当的$ g $ $ g $的子图的色度小于$ k $。图形类别的$ k $ -VERTEX-CRICATION图是算法图理论中的一个重要主题，因为如果给定的遗传图中的此类图的数量是有限的，那么有多项式时间算法可以决定类中的图表是否为$（k-1）$ - 可着色。 在本文中，我们启动了对$ p_5 $ - free图的子类中$ k $ - vertex-关键图的有限性的系统研究。我们的主要结果是对$（P_5，H）$的$ K $ -VERTEX-CRICATION图的有限性进行完整分类 - 所有图表上的所有图表$ h $在4个顶点上的免费图。为了获得完整的二分法，我们使用各种技术（例如Ramsey-Type参数和Dilworth的定理双重）证明了四个新图$ H $的有限性 - 可能具有独立的利益。
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we initiate a systematic study of the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworth's Theorem -- that may be of independent interest.
