图的k-全染色问题与Grobner基求解

熊雪玮^1,3 刘培江² 王浩华¹

出版日期:2019-06-30 发布日期:2020-08-01
通讯作者: 王浩华，男，教授. E-mail:huazi@hainanu.edu.cn
基金资助:
国家自然科学基金（11761025，11901114）;广东省教育厅青年创新人才类（2017KQNCX081）;广州市科技创新一般项目（201904010010）；中山大学广东省计算科学重点实验室开放课题基金资助（2018001）；海南省研究生创新科研课题项目（Hys2019-59）.

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

关键词: 图 , k-全染色 , 极小全染色 , 全染色数 , Grobner基

熊雪玮刘培江王浩华 . 图的k-全染色问题与Grobner基求解[J]. 数学理论与应用, 2019, 39(2): 20-31.

[1]	马红霞赵娟冯艳秋. 两个有向圈笛卡尔积的双控制数[J]. 数学理论与应用, 2021, 41(2): 57-.
[2]	王永威刘伟俊冯立华 . 双循环群上连通凯莱图的数目[J]. 数学理论与应用, 2021, 41(2): 64-.
[3]	蓝婷凌波 . 4p阶11度对称图[J]. 数学理论与应用, 2021, 41(2): 76-.
[4]	黎小丽李时敏孔盈莹 . 基于IGGⅢ权函数的稳健ARMA残差控制图构建[J]. 数学理论与应用, 2021, 41(2): 83-.
[5]	卢俊颖刘伟俊鲁卢 . 图的强和与强积导出的距离整谱图[J]. 数学理论与应用, 2021, 41(1): 33-.
[6]	钱美兰顾辰妍. 一类积图的局部边路替换的L(2,1)-标号[J]. 数学理论与应用, 2019, 39(1): 22-30.

PDF