Color $2$-switches and neighborhood$\lambda$-balanced graphs with$k$ colors

この論文は、グラフの頂点近傍における色の分布を制約する「カラー 2-スイッチ」と「カラー次数行列」を導入して同値性を証明し、さらに $k$ 色の近傍 $\lambda$-平衡グラフの 4 つのクラスを定義して、パスや木などの特定のグラフ族における平衡数に関する結果を導出する。

要約

1. 物語の舞台：「色付きの村」と「近所のバランス」

まず、この研究の世界を想像してください。
そこには**「村（グラフ）」があり、家（頂点）と道（辺）でつながっています。私たちは、この村の各家に「赤」「青」「緑」などの色**を塗る作業をしています。

• 従来のルール（正則彩色）： 「隣の家とは違う色にしなさい！」という厳しいルールでした。
• この論文のルール： 「隣の色が同じでも OK。でも、**『自分の家の周りにある色のバランス』**が大事！」という新しいルールです。

例えば、ある家の周りに「赤い家 3 軒、青い家 3 軒」あれば、それは**「完璧なバランス（0 バランス）」です。もし「赤 4 軒、青 2 軒」なら、少しバランスが崩れています（差が 2）。
この研究は、「どのくらいバランスが崩れても許されるか（λ）」**を最小限に抑えながら、どんな村でも色を塗れるか、またそのルールを満たす村同士はどのように変換できるかを調べています。

---

2. 新しい道具：「色 2-スイッチ（Color 2-switch）」

研究の前半では、**「色 2-スイッチ」**という魔法のような道具を紹介しています。

• どんな魔法？
  2 軒の赤い家（A, B）と 2 軒の青い家（X, Y）がいたとします。
  今、A と X がつながっていて、B と Y がつながっているとします。
  この 2 本の道（A-X, B-Y）を一度消して、A-Y と B-X に作り変えるのです。

• 何がすごい？
  この操作をしても、「各家の周りにある色の数（バランス）」は全く変わりません。
  村の形は変わっても、住民たちが「私の周りには赤が 3 人、青が 2 人」と感じている状況は保たれるのです。

• 発見：
  「2 つの村が、同じ『色のバランス』を持っているなら、必ずこの『色 2-スイッチ』を繰り返すことで、片方からもう片方へ変換できる！」という定理を証明しました。
  これは、**「同じレシピ（バランス）なら、どんな料理（グラフ）も、材料の入れ替え（スイッチ）で作り変えられる」**と言っているのと同じです。

---

3. 新しい分類：「バランスの厳しさを調整する」

以前の研究では、「隣の色が完全に同じ数でなければならない（差 0）」という厳しいルールしかありませんでした。しかし、現実の村では、奇数人の家があったりして、完全なバランスは不可能な場合があります。

そこで、この論文は**「許容範囲（λ）」**という緩いルールを導入しました。

• λ=0： 完全なバランス（赤と青の数が同じ）。
• λ=1： 赤と青の数の差が「1 以内」なら OK。
• λ=2： 差が「2 以内」なら OK。

さらに、**「家の外側だけ（N(v)）」を見るか、「自分も含めた中（N[v]）」を見るか、あるいは「家ごとにルールを変えても OK」**にするかという 3 つのタイプを定義しました。

これにより、**「どんな村でも、ある程度のバランス（λ）を保つ色塗り方が存在する」**ことが示されました。

---

4. 特別なケース：「パリティ（偶奇）バランス」

特に「赤と青の 2 色」の場合、面白いルールが追加されました。
**「パリティバランス（Parity Balanced）」**という概念です。

• ルール：
  • 家の数（次数）が偶数なら、「外側の家の色」をバランスさせます。
  • 家の数（次数）が奇数なら、「自分を含めた家の色」をバランスさせます。

これは、**「偶数の家には偶数のルール、奇数の家には奇数のルール」**を適用するという、状況に応じた柔軟なアプローチです。

---

5. 具体的な結果：「道（パス）」「輪（サイクル）」「車輪（ホイール）」など

研究者たちは、具体的な村の形（道、輪、車輪、木、など）に対して、「どれくらいのバランス（λ）が必要か」を計算しました。

• 例： 「車輪（ホイール）」という形（真ん中に 1 つ、周りに輪っか）では、周りが奇数個のときは少しバランスが崩れる（λ=1）必要があるが、偶数個のときは完璧（λ=0）にできる、といった詳細なルールを見つけました。
• 完全多部グラフ： 「すべての家同士がつながっているような複雑な村」についても、バランスを保つための条件を完全に解明しました。

---

6. まとめ：この研究は何を意味する？

この論文は、**「バランス」という概念を、数学の厳密さから「現実的な柔軟さ」**へと広げました。

• 農業の例え：
  畑（グラフ）に、トマト（赤）とナス（青）を植えるとき、隣り合う区画で「トマトとナスの数が同じ」だと理想的ですが、土地の形によっては不可能かもしれません。
  この研究は、「**『差が 1 つくらいなら許容する』**というルールにすれば、どんな形的土地でも、バランスの取れた植え方が可能だ」と証明し、さらに「同じバランスの畑同士は、植え替え（スイッチ）で自由に行き来できる」ことを示しました。

• 応用：
  この考え方は、実験計画（どの実験条件を隣に置くか）、ネットワーク設計、資源配分など、**「隣り合う要素のバランスをどう最適化するか」**というあらゆる分野に応用できる可能性があります。

要するに、**「完璧でなくてもいい、少しのズレは許容しよう。そうすれば、どんな複雑な世界でも、美しいバランスを見つけられる」**という、数学的な勇気と柔軟性を示した論文なのです。

技術概要

論文「Color 2-switches and neighborhood λ-balanced graphs with k colors」の技術的サマリー

1. 概要

本論文は、グラフの頂点彩色（必ずしも正則彩色とは限らない）において、各頂点の近傍（隣接頂点の集合）に現れる色の分布に制約を課す問題を扱っています。著者らは、色 2-スイッチ（color 2-switches）という操作と色次数行列（color degree matrix）を導入し、$k$ 色の彩色を持つグラフ同士の同値性を特徴づける定理を証明しました。さらに、従来の「近傍平衡彩色（neighborhood balanced coloring）」を $k$ 色へ一般化し、近傍内の各色の頂点数の差を許容する$\lambda$-平衡彩色の概念を提案し、その性質や最小の許容差 $\lambda$（平衡数）を様々なグラフクラスに対して決定しました。

2. 問題設定と背景

• 背景: 従来の研究（Freyberg & Marr [5], Collins et al. [4]）では、2 色（赤・青）を用い、各頂点の近傍（開近傍 $N(v)$ または閉近傍 $N[v]$）において赤と青の頂点数が「完全に等しい」平衡彩色（NBC, CNBC）が研究されていました。これらはすべての頂点が偶数次または奇数次であることを要求するため、適用範囲が限られていました。
• 課題: より一般的なグラフクラス（偶数次と奇数次の頂点が混在するものなど）や、$k$ 色（$k > 2$）の状況下で、近傍内の色のバランスをどのように定義・評価するか、またその平衡性を保ちながらグラフを変換する操作は何かを明らかにすること。
• 目的:
  1. 色次数行列が等しいグラフ同士の関係性を、色 2-スイッチを用いて特徴づける。
  2. $k$ 色、$\lambda$-平衡（各色の頂点数の差が $\lambda$ 以下）という柔軟な条件を定義し、その平衡数（最小の $\lambda$）を研究する。
  3. 特に $k=2, \lambda \le 1$ の重要なケースにおいて、4 つのグラフクラス（OSB, CSB, SBV, PB）を定義し、それらの包含関係と分離例を明らかにする。

3. 手法と主要な概念

3.1 色次数行列と色 2-スイッチ

• 色次数行列 (Color Degree Matrix): $k$ 彩色されたグラフ $G$ に対して、各頂点 $v_i$ について、各色 $j$ に対する次数（$C_j$-deg$(v_i)$）と、頂点自身の色（色識別子）を記録した行列 $D(G)$ を定義します。これは通常の次数列の一般化です。
• 色 2-スイッチ (Color 2-switch): 2 頂点 $u, w$ が同じ色、$x, y$ が同じ色であり、辺 $ux, wy$ が存在し $uy, wx$ が存在しないとき、辺を $uy, wx$ に交換する操作です。
  • 性質: この操作は頂点の色を変えず、各頂点の近傍における各色の頂点数の多重集合も変化させません。したがって、色 2-スイッチを適用しても色次数行列は不変です。
• 主要定理 (Theorem 2.4): 2 つの $k$ 彩色グラフ $G, H$ について、$D(G) = D(H)$ であることと、$G$ から $H$ へ色 2-スイッチの列で変換可能であることは同値です。

3.2 $\lambda$-平衡彩色と平衡数

• 定義: 各頂点 $v$ において、任意の 2 色 $i, j$ について $|C_i\text{-deg}(v) - C_j\text{-deg}(v)| \le \lambda$ となる彩色を $(k, \lambda)$-平衡彩色と呼びます。閉近傍 $N[v]$ についても同様に定義されます。
• 3 つのクラス:
  1. $(k, \lambda)$-平衡：すべての頂点で開近傍 $N(v)$ が $\lambda$-平衡。
  2. $[k, \lambda]$-平衡：すべての頂点で閉近傍 $N[v]$ が $\lambda$-平衡。
  3. $([k, \lambda])$-平衡（局所平衡）：各頂点で、開近傍または閉近傍のどちらかが $\lambda$-平衡であればよい。
• 平衡数: グラフ $G$ に対して、上記の条件を満たす最小の $\lambda$ をそれぞれ $\beta_k(G), \beta_k[G], \beta_k([G])$ と定義します。

3.3 赤青除去 (Red-Blue Removal)

• $k=2$ の場合、$N(x)=N(y)$ となる赤頂点 $x$ と青頂点 $y$ を同時に削除する操作を「赤青除去」と呼びます。この操作を繰り返して得られる簡約グラフを用いることで、完全多部グラフなどの平衡性を解析する手法を提案しました。

4. 主要な結果

4.1 一般論と不等式

• 最大次数 $\Delta$ に対して、$\beta_k(G) \le \Delta$、$\beta_k[G] \le \Delta+1$ などが成り立ちます。
• 平衡数間の関係として、$0 \le \beta_k[G] - \beta_k([G]) \le 1$ などの不等式が示され、これらが厳密であることを例示しました。
• 二部グラフには平衡数が任意に大きくなるものが存在しますが、完全多部グラフでは平衡数が有界（最大 3 以下）であることが証明されました。

4.2 $k=2, \lambda \le 1$ のケース（4 つのクラス）

2 色、許容差 1 以下の条件下で、以下の 4 つのクラスを定義し、その包含関係と分離例を Venn 図（Fig. 9）で示しました。

1. OSB (Open Semi-Balanced): $\beta_2(G) \le 1$（開近傍で平衡）。
2. CSB (Closed Semi-Balanced): $\beta_2[G] \le 1$（閉近傍で平衡）。
3. SBV (Semi-Balanced at each Vertex): $\beta_2([G]) \le 1$（各頂点で開または閉のどちらかが平衡）。
4. PB (Parity Balanced): 偶数次頂点では開近傍で、奇数次頂点では閉近傍で 0-平衡となる彩色が存在する。

包含関係:

• $(PB \cup CSB \cup OSB) \subseteq SBV$
• $(NBC \cup CNBC) \subseteq PB \subseteq (CSB \cap OSB)$

4.3 特定グラフクラスへの適用結果

• パス ($P_n$): 常に OSB $\cap$ CSB に属する。PB に属するのは $n$ が偶数の場合のみ。
• サイクル ($C_n$): 常に CSB。OSB（つまり NBC）に属するのは $n$ が 4 の倍数の場合のみ。
• ホイール ($W_n$): $n$ の値（4 剰余など）によって OSB, CSB, SBV への所属が異なることが詳細に分類されました（例：$W_6$ は CSB だが OSB ではない）。
• 木とキャタピラ: すべての木は OSB に属します。キャタピラ（脊椎と葉からなる木）については、脊椎上の頂点の重み（葉の数）に基づき、PB や CSB に属するための必要十分条件を定理 6.5, 6.7 で完全特徴づけしました。
• 完全多部グラフ: 赤青除去を用いて、OSB, CSB, SBV, PB に属する完全多部グラフの必要十分条件を特徴づけました。また、すべての完全多部グラフについて $\beta_2(G) \le 2, \beta_2([G]) \le 2, \beta_2[G] \le 3$ であることを示しました。

4.4 数え上げ結果

• 脊椎の長さが $n$ である CSB 彩色キャタピラの数 $A(n)$ について、漸化式 $A(n) = 4A(n-1) + 6A(n-2)$ を導出し、明示的な公式と OEIS 数列（A138041）との関連を指摘しました。

5. 意義と貢献

• 理論的貢献: 従来の「完全平衡（0-平衡）」という厳密な条件を緩和し、$\lambda$-平衡というパラメータを導入することで、より広範なグラフクラスを統一的に扱える枠組みを提供しました。
• 操作の一般化: 色 2-スイッチを定義し、色次数行列が不変な変換操作として確立したことは、グラフの彩色構造の同値性を理解する上で重要なツールとなります。
• 応用可能性: 農業計画や実験デザインなど、近傍内のリソース（作物の種類など）のバランスが重要な場面で、厳密な均等ではなく「許容範囲内のバランス」を達成するモデルを提供しています。
• 分類の精緻化: $k=2, \lambda \le 1$ のケースにおける 4 つのクラスの包含関係と、パス、サイクル、ホイール、木、完全多部グラフなど代表的なグラフ族に対する具体的な結果は、今後の研究の基礎となる知見です。

6. 今後の展望

• 距離 2 以内の頂点など、より広範な近傍でのバランスの検討。
• 最適化基準の変更（差の和の最小化など）。
• 辺彩色グラフへの拡張。

本論文は、グラフ彩色の局所的な制約に関する研究を、より柔軟で一般的なパラメータへと発展させ、具体的なグラフクラスに対する詳細な分類と数え上げ結果を提供した点で画期的です。