Caccetta-Hggkvist猜想的注记

作者：梁浩; 徐俊明

来源：数学学报, 2013, (04): 479-486.

• 有向图
• 有向圈
• Caccetta-Hggkvist猜想 digraph
• directed cycle
• Caccetta-Hggkvist conjecture

1978年,Caccetta和Hggkvist提出如下至今仍未解决的猜想:最小出度不小于r的n阶有向图含有长度不大于[n/r]的有向圈.本文证明了:当α≥0.28724时,最小出度至少αn的n阶有向图含有长度不超过4的有向圈.

• 单位
  中国科学技术大学