图的k-全染色问题与Gr?bner基求解

作者：熊雪玮; 刘培江; 王浩华

来源：数学理论与应用, 2019, 39(02): 20-31.

• 图
• k-全染色
• 极小全染色
• 全染色数
• Gr?bner基

对于任意给定的有限图和任一正整数k,本文证明图的k-全染色存在性问题等价于一个多元多项式方程组在{1,2,…,k}范围的求解问题,并通过使用Grbner基给出一个图k-全可染色的有效判别与求解方法,进而求得图的全可染色数与极小全染色方案.