Minimum non-chromatic-choosable graphs with given chromatic number

基本信息

• 论文ID: 2201.02060
• 标题: Minimum non-chromatic-choosable graphs with given chromatic number
• 作者: Jialu Zhu, Xuding Zhu
• 分类: math.CO (组合数学)
• 发表时间: 2024年9月13日
• 论文链接: https://arxiv.org/abs/2201.02060

摘要

图 $G$ 被称为色数可选择的(chromatic-choosable)，如果 $\chi(G) = ch(G)$。一个自然的问题是确定给定色数 $k$ 的非 $k$-可选择图中顶点数的最小值。Ohba猜想并由Noel, Reed和Wu证明：顶点数 $|V(G)| \leq 2k+1$ 的 $k$-色图 $G$ 都是 $k$-可选择的。这个上界是紧的。已知当 $k$ 为偶数时，$G=K_{3*(k/2+1),1*(k/2-1)}$ 和 $G=K_{4,2*(k-1)}$ 是顶点数为 $2k+2$ 的非 $k$-可选择 $k$-色图。本文的主要结果是：所有其他顶点数为 $2k+2$ 的 $k$-色图都是 $k$-可选择的。特别地，如果 $\chi(G)$ 为奇数且 $|V(G)| \leq 2\chi(G)+2$，则 $G$ 是色数可选择的，这证实了Noel的猜想。

研究背景与动机

问题背景

1. 列表着色问题：列表着色是经典图着色的自然推广，由Erdős-Rubin-Taylor和Vizing在1970年代独立引入。对于图 $G$ 的列表分配 $L$，如果存在适当的着色使得每个顶点 $v$ 都着以 $L(v)$ 中的颜色，则称 $G$ 是 $L$-可着色的。
2. 色数可选择图：图 $G$ 被称为色数可选择的，如果其色数 $\chi(G)$ 等于选择数 $ch(G)$。这类图在图论中具有重要地位，与许多困难问题相关。
3. Ohba猜想：Ohba猜想断言对于任意正整数 $k$，顶点数至多为 $2k+1$ 的 $k$-色图都是 $k$-可选择的。该猜想最终由Noel, Reed和Wu在2015年证明。

研究动机

1. 紧性分析：虽然Ohba猜想已被证明，但其紧性问题仍需深入研究。已知的反例仅限于偶数 $k$ 的情况。
2. Noel猜想：Noel猜想对于奇数 $k$，所有顶点数为 $2k+2$ 的 $k$-色图都是 $k$-可选择的。
3. 极值图论：确定给定色数下非色数可选择图的最小顶点数，这是极值图论中的基本问题。

核心贡献

1. 完全刻画：完全刻画了顶点数为 $2k+2$ 的非 $k$-可选择完全 $k$-部图，证明只有 $K_{4,2*(k-1)}$ 和 $K_{3*(k/2+1),1*(k/2-1)}$（当 $k$ 为偶数时）是非 $k$-可选择的。
2. 证实Noel猜想：证明了当 $k$ 为奇数时，每个顶点数至多为 $2k+2$ 的 $k$-色图都是色数可选择的。
3. 精确确定函数 $\beta(k)$：对于函数 $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$，证明了2k + 2, & \text{如果 } k \text{ 为偶数} \\ 2k + 3, & \text{如果 } k \text{ 为奇数} \end{cases}$$
4. 技术创新：引入了"近可接受 $L$-着色"和"伪 $L$-着色"等新概念，发展了新的证明技术。

方法详解

任务定义

设 $G$ 是完全 $k$-部图，$L$ 是 $G$ 的 $k$-列表分配。任务是确定在什么条件下 $G$ 是 $L$-可着色的，特别是当 $|V(G)| = 2k+2$ 且 $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$（当 $k$ 为偶数时）。

核心技术框架

1. 二分图匹配方法

• 基本思想：将 $V(G)$ 划分为独立集族 $\mathcal{S}$，构造商图 $G/\mathcal{S}$
• 二分图构造：构建二分图 $B_\mathcal{S}$，顶点集为 $V(G/\mathcal{S})$ 和 $C_L$，边 $\{v_S, c\}$ 存在当且仅当 $c \in L_S(v_S)$
• Hall定理应用：如果 $B_\mathcal{S}$ 有覆盖 $V(G/\mathcal{S})$ 的匹配，则得到 $L$-着色；否则由Hall定理存在 $X_\mathcal{S} \subseteq V(G/\mathcal{S})$ 使得 $|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|$

2. 伪 $L$-着色概念

定义：$G$ 的伪 $L$-着色是适当着色 $f$，满足：

• $f(v) \in C_L$ 对所有顶点 $v$
• 如果 $f(v) = c \notin L(v)$，则 $f^{-1}(c) = \{v\}$ 是单点 $f$-类

关键性质：

• 如果 $v$ 被错误着色（$f(v) \notin L(v)$），则 $\{v\}$ 必须是单点着色类
• 这为构造部分着色提供了灵活性

3. 近可接受着色

频繁颜色定义：颜色 $c$ 是频繁的，如果满足以下条件之一：

1. $|L^{-1}(c)| \geq k + 2$
2. $|L^{-1}(c) \cap T| \geq \lambda$（其中 $T$ 是单点部的集合）
3. $|T| = \lambda - 1 \geq 1$ 且 $T \subseteq L^{-1}(c)$

近可接受着色：伪 $L$-着色 $f$ 是近可接受的，如果每个被错误着色的顶点都被着以频繁颜色。

证明策略

第一步：排除特殊情况

通过引理2.1处理所有部大小至多为3的完全多部图，建立充分条件使得这类图是 $g$-可选择的。

第二步：反证法框架

假设 $(G,L)$ 是定理1.2的最小反例，即：

• $|V(G)|$ 最小
• 在条件1下，$|C_L|$ 最小

第三步：频繁颜色分析

• 证明至多有 $k-1$ 个频繁颜色（引理7.1）
• 进一步证明至多有 $k-p_1-1$ 个频繁颜色（引理8.3）
• 其中 $p_1$ 是单点部的数量

第四步：最终矛盾

通过构造具有 $k-p_1$ 个频繁颜色的情况，导出矛盾，完成证明。

实验设置

理论验证

本文是纯理论研究，主要通过数学证明验证结果：

1. 小规模验证：对于 $k \leq 7$，直接验证相关图类是 $k$-可选择的
2. 构造性证明：通过具体构造证明某些图确实是非 $k$-可选择的
3. 归纳验证：使用数学归纳法验证引理2.1的条件

关键引理验证

• 引理3.2：如果 $P$ 是 $G$ 的 $2^+$-部，则 $\bigcap_{v \in P} L(v) = \emptyset$
• 引理5.1：关于伪着色中单点数量的上界
• 引理6.1：$G$ 没有近可接受 $L$-着色

实验结果

主要定理验证

定理1.2：设 $G$ 是完全 $k$-部图，$|V(G)| \leq 2k+2$，且当 $k$ 为偶数时 $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$，$L$ 是 $G$ 的 $k$-列表分配，则 $G$ 是 $L$-可着色的。

推论1.3：如果 $k$ 为奇数，则每个顶点数至多为 $2k+2$ 的 $k$-色图都是色数可选择的。

推论1.4：函数 $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ 满足：