染色数为5和6的图中的圈长

doi:10.52396/JUST-2021-0119

中国科学技术大学学报 ›› 2021, Vol. 51 ›› Issue (5): 374-381.DOI: 10.52396/JUST-2021-0119

染色数为5和6的图中的圈长

火清羿^*

中国科学技术大学数学科学学院,安徽合肥 230026

收稿日期:2021-04-17 修回日期:2021-05-25 出版日期:2021-05-31 发布日期:2021-12-01
通讯作者: * E-mail:qyhuo@mail.ustc.edu.cn

Cycle lengths in graphs of chromatic number five and six

Huo Qingyi^*

School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Received:2021-04-17 Revised:2021-05-25 Online:2021-05-31 Published:2021-12-01
Contact: * E-mail: qyhuo@mail.ustc.edu.cn

摘要/Abstract

摘要： Moore和West提出问题:每一个(k+1)-临界的非完全图中是否存在一个模k的意义下长度为2的圈.这里证明了更强的结论:对于k=4, 5,每一个(k+1)-临界的非完全图中一定存在模k的意义下所有长度的圈.

关键词: 圈长, 染色数, 最小度, 广度优先搜索树

Abstract: A problem was proposed by Moore and West to determine whether every (k+1)-critical non-complete graph has a cycle of length 2 modulo k. We prove a stronger result that for k=4, 5, every (k+1)-critical non-complete graph contains cycles of all lengths modulo k.

Key words: cycle length, chromatic number, minimum degree, breadth-first search tree

中图分类号:

O157.5

火清羿. 染色数为5和6的图中的圈长[J]. 中国科学技术大学学报, 2021, 51(5): 374-381.

HUO Qingyi. Cycle lengths in graphs of chromatic number five and six[J]. Journal of University of Science and Technology of China, 2021, 51(5): 374-381.

[1]	李心田, 刘世平. Amply regular图的林-陆-丘曲率和直径[J]. 中国科学技术大学学报, 2021, 51(12): 889-893.
[2]	蔡改香，梅培林，余桂东. 逆度和图的性质[J]. 中国科学技术大学学报, 2020, 50(6): 852-859.
[3]	剧宏娟，雷英杰. 三圈图和四圈图的最大无符号拉普拉斯分离度[J]. 中国科学技术大学学报, 2020, 50(4): 402-408.
[4]	蔡学鹏，杨伟. 折叠交叉立方体的2-外边连通度[J]. 中国科学技术大学学报, 2020, 50(2): 94-99.
[5]	王礼想，余桂东，徐弈. 图的哈密尔顿连通性和从任意点出发都可迹的充分条件[J]. 中国科学技术大学学报, 2020, 50(2): 100-105.
[6]	鲁学星. 顶点偏序集上的平面序[J]. 中国科学技术大学学报, 2018, 48(11): 902-905.
[7]	梁勇，裴利丹，胡夫涛，侯新民. 笛卡尔乘积和直积图的全{k}控制划分数[J]. 中国科学技术大学学报, 2018, 48(8): 605-611.
[8]	洪振木，福克曼·鲁茨，徐俊明. 有向图是极大连通的和超连通的充分条件[J]. 中国科学技术大学学报, 2018, 48(8): 612-617.
[9]	余桂东, 黄冬明, 张午骁, 汪宸. 双圈图和三圈图的最大拉普拉斯分离度[J]. 中国科学技术大学学报, 2017, 47(9): 733-737.
[10]	乔智, 潘永亮. 关于最优强正则图的一个注记[J]. 中国科学技术大学学报, 2017, 47(3): 197-203.
[11]	黄燕云，徐俊明. 容错变形超立方体的圈和路[J]. 中国科学技术大学学报, 2015, 45(6): 436-442.
[12]	洪振木，徐俊明. 超限制边连通笛卡尔乘积图的边容错性[J]. 中国科学技术大学学报, 2014, 44(12): 967-974.
[13]	李小新，查淑萍. 含割点的连通图的最小距离无符号Laplace谱半径[J]. 中国科学技术大学学报, 2014, 44(12): 982-985.

染色数为5和6的图中的圈长

Cycle lengths in graphs of chromatic number five and six

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价