与えられた色数を持つ最小非色数選択可能グラフ

基本情報

• 論文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$ は、$\chi(G) = ch(G)$ である場合、色数選択可能（chromatic-choosable）と呼ばれます。自然な問題として、与えられた色数 $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. リスト着色問題：リスト着色は古典的なグラフ着色の自然な一般化であり、1970年代にErdős-Rubin-TaylorとVizingによって独立に導入されました。グラフ $G$ のリスト割り当て $L$ に対して、各頂点 $v$ が $L(v)$ 内の色で着色される適切な着色が存在する場合、$G$ は $L$-着色可能と呼ばれます。
2. 色数選択可能グラフ：グラフ $G$ は、その色数 $\chi(G)$ が選択数 $ch(G)$ に等しい場合、色数選択可能と呼ばれます。このようなグラフはグラフ理論において重要な地位を占め、多くの困難な問題と関連しています。
3. Ohba予想：Ohba予想は、任意の正整数 $k$ に対して、頂点数が最大 $2k+1$ の $k$-色グラフはすべて $k$-選択可能であると主張しています。この予想は最終的に2015年にNoel、Reed、Wuによって証明されました。

研究の動機

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$ が偶数の場合} \\ 2k + 3, & \text{$k$ が奇数の場合} \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$ であり、以下を満たします：

• すべての頂点 $v$ に対して $f(v) \in C_L$
• $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$ は、誤って着色されたすべての頂点が頻繁な色で着色される場合、準許容です。

証明戦略

第1段階：特殊なケースの除外

引理2.1を通じてすべての部のサイズが最大3の完全多部グラフを処理し、このようなグラフが $g$-選択可能であるための十分条件を確立します。

第2段階：背理法フレームワーク

$(G,L)$ が定理1.2の最小反例であると仮定します：

• $|V(G)|$ が最小
• 条件1の下で、$|C_L|$ が最小

第3段階：頻繁な色の分析

• 最大 $k-1$ 個の頻繁な色が存在することを証明します（引理7.1）
• さらに最大 $k-p_1-1$ 個の頻繁な色が存在することを証明します（引理8.3）
• ここで $p_1$ は単一点部の数です

第4段階：最終的な矛盾

$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)\}$ は以下を満たします：