论文标题
围绕大小和色数的图形对于无效
Graphs with large girth and chromatic number are hard for Nullstellensatz
论文作者
论文摘要
我们基于希尔伯特的无效stellensatz来研究方法的计算效率，该方法使用线性方程式系统来检测具有大周长和色数的图形的非色性。我们表明，对于每一个具有$ n $ vertices和girth $ g> 4k $的非$ k $ - 色彩图，算法是为了求解尺寸至少$ n^{ω（g）} $所需的算法，以检测其非$ k $ - 可溶性。
We study the computational efficiency of approaches, based on Hilbert's Nullstellensatz, which use systems of linear equations for detecting non-colorability of graphs having large girth and chromatic number. We show that for every non-$k$-colorable graph with $n$ vertices and girth $g>4k$, the algorithm is required to solve systems of size at least $n^{Ω(g)}$ in order to detect its non-$k$-colorability.
