Groebner基理论在图着色问题中的应用

摘要：

将Groebnet基理论应用于图着色问题,给出图是否为K-可着色的一种判定方法。通过对图的不同顶点所对应的不同变元建立多项式方程组,计算其字典序下的Groebner基,根据Groebner基是否含单位元1,判定图是否为K-可着色的。给出的2个例子具体说明该方法的计算和判定过程。

关键词： Groebnet基 字典序 图着色 多项式方程组 计算分析

作者: 齐紫微 韩德 董玉才 李红燕 张玲

作者单位: 装甲兵工程学院 基础部,北京 100072

会议类型: 国内会议

会议名称: 2008年国防科技工业与数学学术研讨会

会议地点: 乌鲁木齐

会议语种:中文

页码: 119-121

在线出版日期: 2008-07-25（万方平台首次上网日期，不代表论文的发表时间）