论文标题
对顶点关键的结构（$ p_5 $，gem） - 免费图表的完善
A refinement on the structure of vertex-critical ($P_5$, gem)-free graphs
论文作者
论文摘要
我们提供了一个新的，更强有力的证据，证明只有许多$ k $ - vertex-Critical（$ P_5 $，〜GEM） - 所有$ k $的free Graphs。我们的证明进一步完善了这些图表的结构，并允许实现简单的详尽计算机搜索，以完全列出所有$ 6 $ - 和$ 7 $ -VERTEX-CLICAINAT-COMILITION $（P_5 $，GEM） - 免费图形。我们的结果意味着存在多项式认证算法，以决定$ k $ - 颜色的$（p_5 $，gem） - 所有$ k $的free Graphs，其中证书是$ k $ - 彩色或$ k $ - 彩色或$（k+1）$ - $ - $ 1）$ - dertex-dertex-Crigital crockation-Crock toccuctuse sublaph。我们的$ k \ le 7 $的完整列表允许实现所有$ k \ le 6 $的这些算法。
We give a new, stronger proof that there are only finitely many $k$-vertex-critical ($P_5$,~gem)-free graphs for all $k$. Our proof further refines the structure of these graphs and allows for the implementation of a simple exhaustive computer search to completely list all $6$- and $7$-vertex-critical $(P_5$, gem)-free graphs. Our results imply the existence of polynomial-time certifying algorithms to decide the $k$-colourability of $(P_5$, gem)-free graphs for all $k$ where the certificate is either a $k$-colouring or a $(k+1)$-vertex-critical induced subgraph. Our complete lists for $k\le 7$ allow for the implementation of these algorithms for all $k\le 6$.
