Uniquely colourable graphs and the hardness of colouring graphs of large girth
Uniquely colourable graphs and the hardness of colouring graphs of large girth
复制标题
DOI：
10.1017/s0963548398003678
复制
发表时间：
1998-12-01
影响因子：
0.9
通讯作者：
Kreuter, B
中科院分区：
文献类型：
--
作者：
Emden-Weinert, T;Hougardy, S;Kreuter, B
对任意整数k，我们证明了存在一个至多k（12（g+1））个顶点围长至少为g且最大度至多为5 k（13）的唯一k-列图.由此我们推论，除非NP = RP，否则围长g（G）大于或等于log\G\/13 log k且最大度Delta（G）小于或等于6 k（13）的图G的k-可染性不存在多项式时间算法.我们还研究了几个相关的问题。
For any integer k, we prove the existence of a uniquely k-colourable graph of girth at least g on at most k(12(g+1)) vertices whose maximal degree is at most 5k(13). From this we deduce that, unless NP = RP, no polynomial time algorithm for k-Colourability on graphs G of girth g(G) greater than or equal to log\G\/13 log k and maximum degree Delta(G) less than or equal to 6k(13) can exist. We also study several related problems.