2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge

For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $Ï_1,\cdots,Ï_k$ such that $Ï_i(v)\neÏ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $Ï^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $Ï^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $Ï^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $Ï^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $Ï^{\star}_{\ell}(G)=4$, which matches the known upper bound $Ï^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $Ï^{\star}_{\ell}$ for correspondence coloring, $Ï^{\star}_c$. In fact, all bounds stated above for $Ï^{\star}_{\ell}$ also hold for $Ï^{\star}_c$.

academic

平面グラフのリストパッキングと対応パッキング

基本情報

論文ID: 2401.01332
タイトル: List Packing and Correspondence Packing of Planar Graphs
著者: Daniel W. Cranston (Virginia Commonwealth University)、Evelyne Smith-Roberge (Georgia Tech)
分類: math.CO (組合数学)
発表日: 2024年12月6日 (arXiv第3版)
論文リンク: https://arxiv.org/abs/2401.01332

概要

本論文は平面グラフのリストパッキング(list packing)と対応パッキング(correspondence packing)問題を研究する。グラフ $G$ とリスト割り当て $L$ に対して、すべての頂点 $v$ について $|L(v)|=k$ が成り立つとき、 $L$ -パッキングは $L$ -着色 $\phi_1,\cdots,\phi_k$ を含み、すべての $v$ と異なる $i,j\in\{1,\ldots,k\}$ に対して $\phi_i(v)\neq\phi_j(v)$ を満たす。 $\chi^{\star}_{\ell}(G)$ を、すべての $|L(v)|=k$ のリスト割り当て $L$ に対して $G$ が $L$ -パッキングを持つような最小の $k$ 値とする。本論文は以下を証明した：(i) 周囲長が3以上のすべての平面グラフ $G$ に対して $\chi^{\star}_{\ell}(G)\leq 8$ ；(ii) 周囲長が4以上のすべての平面グラフ $G$ に対して $\chi^{\star}_{\ell}(G)\leq 5$ ；(iii) 周囲長が5以上のすべての平面グラフ $G$ に対して $\chi^{\star}_{\ell}(G)\leq 4$ 。これらの結果は対応着色の類似パラメータ $\chi^{\star}_c$ についても成立する。

研究背景と動機

中心的問題：平面グラフのリストパッキング数と対応パッキング数の上界問題を研究する。リストパッキングはリスト着色の一般化であり、互いに素な複数のリスト着色を見つけることが要求される。
問題の重要性：
- リスト着色は図論における古典的問題であり、広範な理論的および応用的価値を有する
- パッキング問題は着色問題の自然な一般化であり、資源配分の最適化を研究する
- 平面グラフは重要なグラフクラスとして、その着色性質は特別な理論的意義を持つ
既存の制限：
- Cambieら(2024)の研究では、すべての平面グラフ $G$ に対して $\chi^{\star}_c(G)\leq 10$ が証明されている
- しかしこの界限は比較的粗く、さらなる改善が必要である
- 異なる周囲長を持つ平面グラフに対する精密な分析が不足している
研究動機：
- 既知の上界を改善する、特にCambieらが提起した問題を改善する
- 周囲長とパッキング数の間の正確な関係を確立する
- 対応着色に対する統一的な分析枠組みを提供する

中心的貢献

平面グラフのパッキング数上界の顕著な改善： $\chi^{\star}_c(G)\leq 10$ を $\chi^{\star}_c(G)\leq 8$ に改善
周囲長とパッキング数の正確な関係を確立：
- 周囲長≥4： $\chi^{\star}_c(G)\leq 5$
- 周囲長≥5： $\chi^{\star}_c(G)\leq 4$ （最適）
完全に手作業で検証可能な証明を提供：同時期の研究と異なり、計算機検証を回避
リストパッキングと対応パッキングを統一的に処理：すべての結果は両方のパッキングに適用可能
周囲長≥5の場合の最適性を証明：構成例を通じて界限が厳密であることを示す

方法の詳細

タスク定義

リストパッキング：グラフ $G$ と $k$ -割り当て $L$ （各頂点 $v$ に対して $|L(v)|=k$ 個の利用可能な色）が与えられたとき、 $k$ 個の $L$ -着色 $\phi_1,\ldots,\phi_k$ を見つけて以下を満たす：

各 $\phi_i$ は合法的な $L$ -着色である
任意の頂点 $v$ と異なる $i,j$ に対して、 $\phi_i(v)\neq\phi_j(v)$ が成立

対応パッキング：類似の定義だが、リスト着色の代わりに対応着色を使用し、制約がより強い。

中心的技術枠組み

1. 補助二部グラフ法

定義：頂点 $v$ と既存のパッキング $\phi$ に対して、補助二部グラフ $H_v$ を構成
部分A： $k$ 種類の色を表現
部分B： $k$ 個の着色 $\phi_1,\ldots,\phi_k$ を表現
辺： $i\phi_j \in E(H)$ 当且つつ $\phi_j(v)=i$ を設定できる場合のみ

2. Hall定理の応用

二部グラフが完全マッチングを持つかどうかを判定するためにHall定理を利用：

障害：集合 $X \subseteq A$ が $|N(X)| < |X|$ を満たす
重要な観察： $(s,t)$ -二部グラフにおける障害のサイズは制限される

放電法：各頂点に初期電荷として次数を割り当てる
放電規則：各3次頂点は各隣接点から $1/3$ の電荷を受け取る
禁止配置：
- 3次頂点は隣接できない
- $d(v)=3$ かつ $d(w) \leq 4$ となる辺 $vw$ が存在しない
- 5次頂点は最大3個の3次頂点と隣接

2. 周囲長≥5の場合（定理15）

より精密な分析を使用：

重要補題： $(4,2)$ -二部グラフの各頂点は少なくとも2本の1-因子に含まれる辺に関連付けられている
経路分析：3次頂点から構成される経路 $xvy$ の処理に焦点
再パッキング技術：隣接頂点の着色を修正することで、目標頂点の拡張空間を作成

3. 一般平面グラフの場合（定理19）

Borodin構造定理： $\delta(G) \geq 5$ の平面グラフは三角形 $uvw$ を含み、 $d(u)+d(v)+d(w) \leq 17$ を満たす
障害タイプ分析：4種類の障害タイプを定義し、それぞれ処理
複雑な再パッキング：2つの頂点の着色を同時に修正する必要がある場合がある

タイプ1： $|X|=5$ 、 $|N(X)|=3$
タイプ2： $|X|=4$ 、 $|N(X)|=3$ 、かつ特定の拡張構造が存在
タイプ3：タイプ2に類似だが拡張構造が異なる
タイプ4：前三つに属さない $|X|=4$ 、 $|N(X)|=3$ の場合

2. 統一分析枠組み

補題8を通じてリスト着色と対応着色の等価性を確立し、木構造上で配置を「直線化」することを可能にする。

3. 正確な次数制約

オイラー公式を利用して周囲長と平均次数の関係を確立：

周囲長 $g$ の平面グラフの最大平均次数 $< 2g/(g-2)$
周囲長4：平均次数 $< 4$
周囲長5：平均次数 $< 10/3$

主要な結果

定理の陳述

定理1：すべての平面グラフ $G$ に対して $\chi^{\star}_c(G) \leq 8$ が成立
定理2：周囲長≥4のすべての平面グラフ $G$ に対して $\chi^{\star}_c(G) \leq 5$ が成立
定理3：周囲長≥5のすべての平面グラフ $G$ に対して $\chi^{\star}_c(G) \leq 4$ が成立し、この界限は最適である

最適性

環 $C_k$ （ $k \geq 3$ ）の例を通じて証明：

$\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)$
対応パッキングはリストパッキングより困難であることを示す
周囲長≥5の場合の界限4は厳密である

結論と議論

主要な結論

平面グラフのパッキング数の上界を顕著に改善
周囲長とパッキング数の正確な関係を確立
完全に構成的な証明方法を提供
リストパッキングと対応パッキングを統一的に処理

制限事項

証明は技術的であり、多くの場合分析を含む
一般的な曲面上のグラフについてはまだ解決されていない
特定の界限の最適性はまだ完全には確定されていない

将来の方向

論文は6つの開放問題を提起している：

$\chi^{\star}_\ell(\mathcal{P}_3)$ と $\chi^{\star}_\ell(\mathcal{P}_4)$ の正確な値を決定する
最大平均次数が有界なグラフクラスのパッキング数を研究する
平面二部グラフのパッキング数問題
一般的な曲面上のグラフのパッキング数
Heawood数との関係
完全部分グラフを含まないグラフのパッキング数

深い評価

利点

理論的貢献が重大：重要な問題の界限を顕著に改善
方法の革新性：障害分類と統一分析枠組みは普遍的な意義を持つ
証明の完全性：計算機検証を回避し、すべての証明は手作業で検証可能
結果の最適性：周囲長≥5の場合は最適界限に達する
記述の明確性：技術的詳細は良く組織され、例は理解を助ける

不足点

証明の複雑性：多くの技術的詳細と場合分析
推広性：他のグラフクラスへの方法の適用可能性が不明確
計算複雑性：アルゴリズムの複雑性については議論されていない

影響力

理論的価値：グラフ着色理論の発展を推進
方法的価値：技術ツールは他の問題に適用可能である可能性
開放問題：提起された問題は後続研究の方向を提供

適用シーン

資源配分における競合回避
スペクトラム割り当てとネットワーク着色
スケジューリング問題における制約充足
組合せ最適化におけるパッキング問題

参考文献

論文は20篇の重要な文献を引用しており、以下を含む：

平面グラフの構造に関するBorodinの古典的結果
パッキング問題に関するCambieらの開拓的研究
対応着色に関するDvořák-Postleの理論
曲面グラフ着色に関するHeawood古典理論

本論文は組合せ数学、特にグラフ着色理論において重要な貢献をしており、精巧な技術手段を通じて平面グラフのパッキング問題の界限を顕著に改善し、当該分野のさらなる発展のための堅実な基礎を築いている。