Precoloring 3-extension on outerplanar graphs

この論文は、三角形を最大 2 つ含む連結な外平面グラフにおいて、2 つまたは 3 つの非隣接頂点に事前着色された色を、グラフ全体への 3 色彩色に拡張可能であることを示しています。

要約

この論文は、**「地図の色塗り」**というパズルにまつわる、とても面白い数学的な発見について書かれています。

専門用語を全部捨てて、**「お城の城壁」や「宝石」**の物語として説明してみましょう。

1. 物語の舞台：平らな世界と「三角形の城」

まず、この話の舞台は**「平らな世界（平面グラフ）」です。ここには、線（道）でつながった点（町）がたくさんあります。
この世界には、「三角形（3 つの町がぐるりとつながった形）」**という特別な構造があります。

• グロツシュの定理（昔の偉大な発見）：
  昔、ある数学者が「もしこの世界に『三角形の城』が一つもなければ、たった 3 色だけで全ての町を綺麗に塗り分けられるよ！」と証明しました。
• 最新の発見：
  さらに最近、「三角形の城が 1 つだけあっても、3 色で塗れるよ！」という発見がありました。

2. 今回の挑戦：「色を指定された町」の問題

今回の論文のテーマは、**「予色付け（プレカラーリング）」**というゲームです。

ゲームのルール：
「いくつかの町には、すでに『赤』『青』『黄』のどれかが塗られています。この状態で、残りの町を 3 色だけで綺麗に塗り分けられるでしょうか？」

通常、もし「赤」の町が隣り合っていたり、配置が悪かったりすると、3 色では塗り分けられなくなってしまうことがあります。
でも、この論文の著者たちは、**「外側（外周）にしか町がない『外平面グラフ』」**という特別な世界で、以下のことが成り立つことを証明しました。

• 三角形が 1 つしかない世界： 3 つの独立した町（互いに隣り合っていない町）に色を指定しても、必ず塗り分けられる。
• 三角形が 2 つしかない世界： 2 つの独立した町に色を指定しても、条件付きで必ず塗り分けられる。

3. 最大の敵：「ダイヤモンドの罠」

ここで、この世界に**「ダイヤモンド（D）」**という特別な構造が登場します。
これは、2 つの三角形が「共通の辺」をくっつけて、ひし形（ダイヤモンド）の形を作っているものです。

• ダイヤモンドの呪い：
  このダイヤモンド構造の中で、特定の 2 つの町（ダイヤモンドの頂点）は、**「必ず同じ色で塗らなければならない」**という呪いにかかっています。
  もし、プレイヤーが「この 2 つの町は違う色で塗ってね」と指定してしまったら、もう 3 色では塗り分けられなくなってしまいます（パズルが崩壊します）。

この論文は、**「ダイヤモンドの呪いがある場合でも、指定された 2 つの町が『同じ色』なら、あるいは『ダイヤモンドの呪いに関係ない位置』なら、必ず成功するよ！」**と教えています。

4. 解決の鍵：「色調整アルゴリズム」と「魔法の鏡」

では、どうやって証明したのでしょうか？著者たちは**「色調整アルゴリズム」**という魔法を使いました。

• イメージ：
  地図全体を、小さな「四角い部屋（4 面）」や「五角形の部屋（5 面）」に分割します。
  各部屋には、**「鏡（ホモモルフィズム）」**が設置されています。この鏡は、部屋の壁の色を「赤・青・黄」の 3 色に変換するルールを持っています。

• アルゴリズムの動き：

  1. まず、指定された町（例えば A 町と B 町）に色を塗ります。
  2. 鏡を通して、隣の部屋の色を次々と決めていきます。
  3. もし、B 町に塗ろうとした色が、すでに決まっている隣の色と衝突しそうになったら、**「鏡のルールを少し変える（色をずらす）」**という操作を行います。
  4. この操作は限られた回数で終わるので、計算機でも瞬時に解けます。

このようにして、「ダイヤモンドの呪い」さえクリアすれば、どんなに複雑な配置でも、3 色だけで完璧に塗り分けられることを示しました。

5. まとめ：何がすごいのか？

この論文のすごさは、**「制約（三角形の数や、指定された色の位置）」と「自由（3 色で塗り分けられるかどうか）」**のバランスを、非常に細かく解明した点にあります。

• 三角形が 1 つなら： 3 つの町を自由に指定しても OK。
• 三角形が 2 つなら： 2 つの町を指定するが、「ダイヤモンドの呪い」には気をつける必要がある。

これは、地図作成や回路設計、スケジュール管理など、**「限られた資源（色）で、制約条件を満たしながら全体を最適化する」**という現実世界の課題に応用できる、美しい数学的な指針となっています。

一言で言うと：
「三角形が 1 つか 2 つしかない平らな地図なら、いくつかの町に色を指定しても、『ダイヤモンドの罠』さえ避ければ、3 色だけで必ず綺麗に塗り分けられるよ！」という、パズル好きのための究極の攻略本です。

技術概要

1. 問題設定 (Problem)

事前彩色拡張問題とは、グラフの特定の部分集合の頂点に事前に色を割り当てたとき、その部分彩色を全体のグラフの適切な $k$ 彩色（ここでは $k=3$）に拡張できるかどうかを決定する問題です。

• 背景:
  • Grötzsch の定理（1958 年）は、「三角形を含まない平面グラフは 3 彩色可能である」という有名な結果です。
  • 近年、La ら [6] が、三角形を最大 1 つ含む平面グラフにおける 3 彩色拡張に関する結果（定理 1.1, 1.3）を導き出しました。
  • La らは、三角形を 2 つ含む場合や、特定の構造（ダイヤモンド構造など）を持つ場合の拡張可能性について未解決の問題（Problem 4.2, 4.3, 4.4）を提起しました。
• 本研究の焦点:
  • La らが提起した問題のうち、三角形を最大 2 つ含む連結外平面グラフにおいて、独立した 3 つの頂点（または独立した 2 つの頂点）に事前彩色を与えた場合、その彩色が全体の 3 彩色に拡張可能かどうかに焦点を当てています。

2. 手法と定義 (Methodology)

本研究では、以下の概念と手法を組み合わせて証明を行っています。

• ダイヤモンド構造 (Diamond D):
  • 2 つの三角形が 1 つの辺を共有する構造を「ダイヤモンド D」と定義します。
  • この構造において、共有しない 2 つの独立した頂点（ダイヤモンド頂点）は、任意の適切な 3 彩色において同じ色でなければならないという制約が生じます。
• 三角形の分類:
  • 外平面グラフの埋め込み（H-embedding）に基づき、三角形を以下のように分類します。
    • 内側三角形 (Inner triangle): 外境界と辺を共有しない三角形。
    • 縞三角形 (Striped triangle): 外境界と 1 辺を共有する三角形。
    • 境界三角形 (Marginal triangle): 外境界と 2 辺を共有する三角形。
• ホモモルフィズム (Homomorphism) とアルゴリズム:
  • 面（4 面や 5 面）から $K_3$（完全グラフ 3 頂点）へのホモモルフィズム写像を定義し、彩色パターンを記述します。
  • 彩色調整アルゴリズム (Algorithm 1): 事前彩色された 2 つの独立頂点が同じ色になるように、ホモモルフィズム写像を順次適用・調整するアルゴリズムを提案しました。これにより、隣接する面の制約を満たしつつ、目標の頂点の色を一致させることが可能であることを示しています。
• グラフ変形:
  • 証明の過程で、グラフに弦（chord）を追加して面長を 5 以下に制限したり、特定の頂点や辺を削除して部分グラフ（三角形数が 1 つのグラフなど）に帰着させ、既知の定理（Grötzsch 定理や La らの結果）を適用する手法を用いています。

3. 主要な貢献と結果 (Key Contributions & Results)

本研究は、2 連結外平面グラフおよび 1 連結外平面グラフに対して、以下の定理と帰結を確立しました。

定理 1.5 (三角形を 1 つ含む 2 連結外平面グラフ)

• 結果: 三角形を 1 つ含む 2 連結外平面グラフにおいて、任意の 3 つの独立した頂点に事前彩色を与えた場合、その彩色は全体の 3 彩色に拡張可能です。
• ケース: 3 頂点がすべて異なる色、すべて同じ色、2 つが同じ色でもう 1 つが異なる色のすべてのパターンを網羅的に証明しました。

定理 1.6 (三角形を 2 つ含む 2 連結外平面グラフ)

• 結果: 三角形を 2 つ含む 2 連結外平面グラフにおいて、任意の 2 つの独立した頂点に事前彩色を与えた場合、以下の 3 つの条件のいずれかを満たせば、その彩色は全体の 3 彩色に拡張可能です。
  1. グラフが「ダイヤモンド D」を部分グラフとして含まない。
  2. グラフがダイヤモンド D を含むが、事前彩色された 2 つの非隣接頂点がダイヤモンドの頂点を最大 1 つしか共有しない。
  3. グラフがダイヤモンド D を含み、事前彩色された 2 つの非隣接頂点が「ダイヤモンド頂点」である場合、それらは同じ事前彩色でなければならない。

帰結 1.7 と 1.8 (1 連結外平面グラフへの拡張)

• 1 連結外平面グラフは、辺の追加によってある 2 連結外平面グラフの部分グラフとして得られるため、上記の定理を適用できます。
• 三角形を 1 つ含む 1 連結グラフでは、3 つの独立頂点の任意の事前彩色が拡張可能です。
• 三角形を 2 つ含む 1 連結グラフでは、定理 1.6 の 3 条件を満たす場合、2 つの独立頂点の事前彩色が拡張可能です。

4. 証明の概要 (Proof Outline)

• 定理 1.5 の証明:
  • 3 つの独立頂点の色の組み合わせ（3 色すべて異なる、すべて同じ、2 つが同じ）ごとに、グラフに新しい頂点と辺を追加して 5 面（5-cycle）を形成し、その面の特殊な辺が三角形に含まれないことを利用して、既知の定理（Theorem 1.4）を適用し拡張可能性を示しました。
• 定理 1.6 の証明:
  • 2 つの独立頂点が異なる色の場合：グラフに辺を追加して平面性を維持できるか確認し、三角形の数が 3 つ以下になるように制御して 3 彩色可能であることを示しました。
  • 2 つの独立頂点が同じ色の場合：
    • 三角形の配置（境界・縞・内側）とダイヤモンド構造の有無に基づいて 6 つのケースに分類しました。
    • ダイヤモンド構造がある場合は、共通隣接点を削除して 4 面に変換し、異なる色で彩色することで帰着させました。
    • ダイヤモンド構造がない場合や、頂点が特定の位置にある場合は、ホモモルフィズムに基づく彩色調整アルゴリズムを用いて、2 頂点が同じ色になるように彩色を調整し、残りのグラフを 3 彩色可能であることを示しました。

5. 意義と結論 (Significance & Conclusion)

• 理論的貢献:
  • Grötzsch の定理の一般化として、三角形を 2 つ含む外平面グラフにおける事前彩色拡張の完全な条件を明らかにしました。
  • La ら [6] が提起した未解決問題（Problem 4.2, 4.3）のうち、外平面グラフの文脈における解答を提供しました。
• 方法論的革新:
  • 外平面グラフの構造的特徴（面長、三角形の位置関係）と、ホモモルフィズム写像を組み合わせることで、複雑な彩色制約を体系的に処理するアルゴリズム的アプローチを提案しました。
  • 「ダイヤモンド構造」が彩色の拡張可能性に与える影響（同色強制など）を明確に定式化しました。
• 今後の展望:
  • 三角形を 3 つ以上含む場合や、より一般的な平面グラフにおける拡張可能性については、まだ多くの未解決問題（Problem 4.4 など）が残されています。本研究は、これらの問題に対する重要な一歩となります。

要約すると、この論文は、外平面グラフにおける 3 彩色の拡張可能性を、三角形の数と「ダイヤモンド構造」の有無という観点から厳密に分類・証明し、事前彩色された頂点の配置条件を明確にすることで、グラフ彩色理論の重要な知見を提供しています。