不含k弦循环图的色有界性证明：Aboulker-Bousquet猜想的大k情形验证

《Forum of Mathematics, Sigma》：Chi-Boundedness of graphs containing no cycles with k chords

本刊推荐：Aboulker与Bousquet于2015年提出猜想：对于任意k≥1，不含恰有k条弦的循环的图族是χ-有界的。本研究通过极值图论与数论工具的结合，证明了当k足够大或k=?(?-2)(?≥3)时该猜想成立。研究团队构建了多层提取结构与单峰路径模型，利用拉格朗日四平方定理的变体精确控制弦数，最终在Forum of Mathematics, Sigma发表突破性成果，为图的色有界性理论提供关键支撑。

　　

在图论研究中，图的染色数与团数之间的关系一直是核心课题。简单来说，团数ω(G)衡量图中最大完全子图的大小，而染色数χ(G)表示对顶点进行正常着色所需的最少颜色数。虽然显然有χ(G)≥ω(G)，但两者之间可能存在的巨大差距令人困惑——比如存在三角形免费却具有任意高染色数的图（Mycielski构造）。针对这一现象，Gyarfás在1987年正式提出χ-有界性概念：若图族G存在函数f使得χ(G)≤f(ω(G))恒成立，则称该图族是χ-有界的。

一个特别引人入胜的方向是研究禁止特定子图的图族。当禁止的图F包含循环时，由于Erd?s证明存在任意大围长（最短循环长度）和高染色数的图，Forb(F)不可能是χ-有界的。然而对于森林F，Gyarfás和Sumner猜想Forb(F)总是χ-有界的，这成为该领域最著名的开放问题之一。Scott证明了弱化版本：禁止细分森林F的图族是χ-有界的，但禁止任意图F的细分图族则不然。

在此背景下，Aboulker和Bousquet提出研究禁止含恰k条弦的循环的图族C_k。这里的“弦”指循环中连接非相邻顶点的边。他们猜想每个C_k都是χ-有界的，并验证了k=1,2,3的情形。本研究通过创新性地结合极值图论与数论方法，证明了该猜想对足够大的k以及k=?(?-2)形式的整数成立，为解决这一猜想迈出决定性一步。

研究团队采用多层提取技术构建证明框架。首先通过K?vári–Sós–Turán定理在高压色数图中找到大型完全二分子图K_?,?，或利用Kühn–Osthus定理获得高连通图的1-细分副本。关键突破在于发现当存在多个无边相连的K_?,?时，可通过单峰路径连接这些子图构建循环，并精确控制弦的数量。特别地，团队证明了若图G的染色数远超团数，则必包含大型诱导二分子图或恰有k条弦的循环。

技术方法上，研究主要依赖：1）基于距离层的图提取技术，构建具有单峰路径特性的多层子图序列；2）利用K?vári–Sós–Turán定理在二分图中定位密集子结构；3）通过Thomas–Wollan链环定理保证顶点不相交路径的存在性；4）创新应用拉格朗日四平方定理的变体，将目标弦数分解为平方和或特定整数形式组合。

4.1 二分子图获取机制

通过极值图论方法证明：给定k,?≥1，存在函数g使得图G要么满足χ(G)≤g(ω(G))，要么包含K_?,?，或包含恰k条弦的循环。该结论将三角形免费图的色有界性结果推广至一般情形。

4.2 三角形处理策略

当图中存在三角形时，通过分析细分顶点与原始顶点的共同父节点关系，构建具有精确弦数的循环。利用κ-连通性保证不相交路径存在，通过精心设计的循环构造控制弦数。

5 数论引理的组合应用

证明每个大整数可表示为20个大于c²的平方数之和（引理5.1），且每个4的倍数大整数可表示为80个a(a+1)形式数之和（引理5.2）。这些结果为近似结果中弦数微调提供数学基础。

6 近似结果的证明路径

首先通过分层提取获得101个无边相连的K_?,?副本。通过单峰路径连接这些副本形成循环，利用数论引理将弦数表示为∑(a_i²+t_ia_i)+O(√k)形式。当t_i奇偶性分布适宜时，可精确得到k条弦；否则获得k至k+3条弦的循环。

7 精确结果的技术突破

通过分析顶点与其三代父节点（对应三个不同层）的关联结构，将交互模式分类为六种情形（K1-K6）。对多数情形直接构造精确弦数循环；对复杂情形通过引入辅助顶点和路径微调，最终实现弦数的精确控制。证明当p-提取图中存在?个无边相连的K_?,?（?》k）时，必存在恰k条弦的循环。

本研究通过创新性地融合极值图论、拓扑图论与数论工具，解决了χ-有界性理论中长期存在的关键问题。定理1.1证实了对足够大k的Aboulker-Bousquet猜想，定理1.2则将Bousquet-Thomassé关于无轮图的色有界性结果推广至含三角形情形。方法学上提出的多层提取结构与单峰路径模型，为后续研究提供了新范式。论文最后提出两个重要发展方向：将结果推广至所有k≥1的完整猜想证明，以及探索更具结构的k-扇子图禁止情形（Conjecture 8.2），为图的染色理论开辟了新航路。