三色可染图中寻找大独立集的困难性
Hardness of finding large independent sets in three-colorable graphs
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究三色可染图中独立集问题的计算复杂性。作者声称对每个固定0<δ<1/3，区分三色可染图与所有独立集大小小于δ倍顶点数的图是NP困难的。由此推出对每个固定整数c≥3，在三色可染图中寻找合法c-着色是NP困难的。该结果对图着色与独立集问题的近似困难性提供了新的下界。摘要未说明归约细节。
- 对每个固定0<δ<1/3，区分三色可染图与独立集小于δn的图是NP困难的。
- 推出对每个固定c≥3，三色可染图的c-着色是NP困难的。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that, for every fixed $`0\lt \delta\lt 1/3`$, it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c-coloring of a three-colorable graph is NP-hard.
用户标记：未标记
固定编号：b9527a4c21096e19
原文来源