2025-11-19T00:34:13.724446

Dominating Hadwiger's Conjecture holds for all $2K_2$-free graphs

Song, Tibbetts
A dominating $K_t$ minor in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise disjoint non-empty connected subgraphs of $G$, such that for $1 \leq i<j\leq t$, every vertex in $T_j$ has a neighbor in $T_i$. Replacing ``every vertex in $T_j$'' by ``some vertex in $T_j$'' retrieves the standard definition of a $K_t$ minor. The strengthened notion was introduced by Illingworth and Wood [arXiv:2405.14299], who asked whether every graph with chromatic number $t$ contains a dominating $K_t$ minor. This is a substantial strengthening of the celebrated Hadwiger's Conjecture, which asserts that every graph with chromatic number $t$ contains a $K_t$ minor. At the ``New Perspectives in Colouring and Structure'' workshop held at the Banff International Research Station from September 29 - October 4, 2024, Norin referred to this question as the ``Dominating Hadwiger's Conjecture'' and believes it is likely false. In this paper we prove that the Dominating Hadwiger's Conjecture holds for all $2K_2$-free graphs. A key component of our proof is the clever use of the existence of an induced banner, obtained by adding a vertex adjacent to exactly one vertex on a cycle of length four.
academic

Dominating Hadwiger's Conjecture holds for all 2K22K_2-free graphs

基本信息

  • 论文ID: 2510.12567
  • 标题: Dominating Hadwiger's Conjecture holds for all 2K22K_2-free graphs
  • 作者: Zi-Xia Song (University of Central Florida), Thomas Tibbetts (University of Central Florida)
  • 分类: math.CO (Combinatorics)
  • 发表时间: 2024年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12567

摘要

本文研究了图论中的一个重要猜想——支配Hadwiger猜想。支配KtK_t子式的定义是图GG中一个序列(T1,…,Tt)(T_1,\dots,T_t)，其中TiT_i是两两不相交的非空连通子图，且对于1≤i<j≤t1 \leq i<j\leq t，TjT_j中的每个顶点都在TiT_i中有邻居。这比标准的KtK_t子式定义更强（后者只需要"某个顶点"而非"每个顶点"）。支配Hadwiger猜想断言每个色数为tt的图都包含一个支配KtK_t子式。本文证明了支配Hadwiger猜想对所有2K22K_2-free图成立，其中2K22K_2表示长度为4的圈的补图。

研究背景与动机

  1. 要解决的问题: 验证支配Hadwiger猜想在特定图类（2K22K_2-free图）上的正确性。
  2. 问题的重要性:
    • Hadwiger猜想是图论中最重要的未解决问题之一，与四色定理等价（对于t≥5t \geq 5）
    • 支配Hadwiger猜想是对经典Hadwiger猜想的实质性加强
    • 该研究有助于理解图的色数与结构特性之间的深层关系
  3. 现有方法的局限性:
    • 经典Hadwiger猜想本身就极其困难，对于t≥7t \geq 7仍然开放
    • 支配版本更加困难，Norin认为该猜想可能是错误的
    • 现有结果仅证明了t≤5t \leq 5的情况
  4. 研究动机: 通过在特定图类上验证支配Hadwiger猜想，为该猜想的真假性提供更多证据，并发展新的证明技术。

核心贡献

  1. 主要定理: 证明了支配Hadwiger猜想对所有2K22K_2-free图成立，即每个2K22K_2-free图GG满足hd(G)≥χ(G)h_d(G) \geq \chi(G)。
  2. 新颖的证明技术: 巧妙地利用了induced banner（在4-圈上添加一个顶点得到的图结构）的存在性。
  3. 结构性洞察: 提供了关于2K22K_2-free图结构特性的深入理解。
  4. 理论贡献: 为支配Hadwiger猜想的研究提供了新的技术工具和分析方法。

方法详解

任务定义

输入: 一个2K22K_2-free图GG（即不包含2K22K_2作为导出子图的图） 输出: 证明hd(G)≥χ(G)h_d(G) \geq \chi(G)，其中hd(G)h_d(G)是图GG的支配Hadwiger数 约束: 图GG必须是2K22K_2-free的

关键概念

  1. 支配KtK_t子式: 序列(T1,…,Tt)(T_1, \ldots, T_t)，其中TiT_i是两两不相交的连通子图，且对1≤i<j≤t1 \leq i < j \leq t，TjT_j中每个顶点都在TiT_i中有邻居。
  2. Banner: 在4-圈C4C_4上添加一个顶点，该顶点恰好与C4C_4上的一个顶点相邻得到的图。
  3. 2K22K_2-free图: 不包含两个不相交边作为导出子图的图。

证明架构

证明采用反证法，假设存在反例GG使得hd(G)<χ(G)h_d(G) < \chi(G)，并选择顶点数最少的这样的图。

关键引理系统:

  1. Claim 1: 如果GG包含导出banner B=(b1,b2,b3,b;b′)B = (b_1, b_2, b_3, b; b')，则存在相邻顶点b4,b5b_4, b_5满足特定的邻接关系。
  2. Claim 2: GG包含C5C_5作为导出子图。
  3. Claim 3: HH中每个顶点与C5C_5上至少4个顶点相邻。
  4. Claims 4-9: 详细分析C5C_5周围顶点的分布和邻接模式。

技术创新点

  1. Banner结构的巧妙运用: 通过分析banner的存在性来控制图的局部结构。
  2. 模运算技巧: 在处理C5C_5上的顶点时使用模5运算，简化了索引处理。
  3. 分类讨论的系统性: 将C5C_5外的顶点按照与C5C_5的邻接模式进行精确分类。
  4. 正则性分析: 证明了某些二部图的正则性质，这是构造支配子式的关键。

实验设置

本文是纯理论研究，不涉及实验验证。所有结果都通过严格的数学证明获得。

实验结果

主要结果

定理1.3: 每个2K22K_2-free图GG满足hd(G)≥χ(G)h_d(G) \geq \chi(G)。

这是本文的核心结果，完全解决了支配Hadwiger猜想在2K22K_2-free图上的问题。

辅助结果

定理1.4: 每个{C4,C5,C6,…,C2α(G)}\{C_4, C_5, C_6, \ldots, C_{2\alpha(G)}\}-free图GG满足hd(G)≥χ(G)h_d(G) \geq \chi(G)。

定理1.5: 对于独立数至多为2的图，在排除某些小图的情况下，支配Hadwiger猜想成立。

与经典结果的对比

定理1.6 (Micu, 2005): 每个2K22K_2-free图GG包含Kχ(G)K_{\chi(G)}子式。

本文的结果是对Micu结果的实质性加强，因为支配KtK_t子式比普通KtK_t子式要求更严格。

相关工作

经典Hadwiger猜想研究

  1. 历史发展: Hadwiger (1943) 和 Dirac (1952) 证明了t≤4t \leq 4的情况
  2. 与四色定理的关系: Wagner (1937) 证明t=5t=5的情况等价于四色定理
  3. 近似结果: Kostochka-Thomason定理给出了Ω(t/log⁡t)\Omega(t/\sqrt{\log t})的下界

支配版本的研究

  1. 概念引入: Illingworth和Wood (2024) 首次提出支配KtK_t子式的概念
  2. 已知结果: t≤4t \leq 4的情况已被验证，Norin宣布了t=5t=5的结果
  3. 一般上界: 每个无支配KtK_t子式的图是2t−22^{t-2}-可着色的

结论与讨论

主要结论

本文成功证明了支配Hadwiger猜想对所有2K22K_2-free图成立，这为该猜想的研究提供了重要的正面证据。

局限性

  1. 适用范围: 结果仅适用于2K22K_2-free图，不能推广到一般图
  2. 构造性: 证明是存在性的，没有给出构造支配子式的有效算法
  3. 技术依赖: 证明高度依赖于2K22K_2-free的假设，技术不易推广

未来方向

  1. 扩展到更大图类: 研究其他禁用子图类上的支配Hadwiger猜想
  2. 算法问题: 开发寻找支配子式的有效算法
  3. 反例构造: 寻找支配Hadwiger猜想的反例

深度评价

优点

  1. 技术创新性: Banner结构的运用非常巧妙，为处理此类问题提供了新思路
  2. 证明严谨性: 9个关键引理环环相扣，逻辑链条完整
  3. 理论意义: 为重要猜想提供了新的正面证据
  4. 写作清晰: 结构化的证明易于理解和验证

不足

  1. 适用范围有限: 仅适用于特定图类，距离解决一般情况还很远
  2. 技术特殊性: 证明技术高度依赖于2K22K_2-free的结构特性
  3. 缺乏算法: 没有提供构造性的算法

影响力

  1. 理论贡献: 为支配Hadwiger猜想研究提供了重要进展
  2. 技术价值: Banner技术可能在其他结构图论问题中有应用
  3. 启发意义: 为在特定图类上研究困难猜想提供了范例

适用场景

该结果主要适用于：

  1. 结构图论的理论研究
  2. 图着色问题的分析
  3. 禁用子图理论的发展

参考文献

主要参考文献包括：

  1. Hadwiger (1943): 原始Hadwiger猜想
  2. Illingworth & Wood (2024): 支配子式概念的引入
  3. Micu (2005): 2K22K_2-free图上经典Hadwiger猜想的证明
  4. Strong Perfect Graph Theorem: 完美图理论的重要结果

总体评价: 这是一篇高质量的理论图论论文，在重要猜想的特定情况下取得了完全的解决。虽然适用范围有限，但技术创新性强，为该领域的进一步研究奠定了基础。