辺彩色

デザルググラフの3辺彩色。辺は3色で彩色できますが、2色で彩色することはできないため、グラフの彩度指数は3です

グラフ理論において、グラフの適切な辺彩色とは、2つの隣接する辺が同じ色にならないように、グラフの辺に「色」を割り当てることです。例えば、右の図は、赤、青、緑の色でグラフの辺を彩色したものです。辺彩色は、グラフ彩色のいくつかの異なる種類の1つです。辺彩色問題は、与えられたグラフの辺を、与えられたkの値に対して最大k 個の異なる色で彩色できるか、あるいは可能な限り少ない色で彩色できるかという問題です。与えられたグラフの辺に必要な最小限の色数は、グラフの 彩度指数と呼ばれます。

ヴィイジングの定理によれば、単純グラフの辺を彩色するために必要な色の数は、その最大次数ΔかΔ+1のいずれかである。二部グラフや高次平面グラフなど、一部のグラフでは色の数は常にΔであり、多重グラフでは色の数は3Δ/2ほどになることがある。二部グラフの最適彩色や、二部でない単純グラフで最大Δ+1色を使用する彩色を構築する多項式時間アルゴリズムが存在する。しかし、最適な辺彩色を見つける一般的な問題はNP 困難であり、そのための最も高速な既知のアルゴリズムでも指数時間がかかる。辺への色の割り当てが非隣接性以外の条件を満たす必要がある辺彩色問題のさまざまなバリエーションが研究されてきた。辺彩色は、スケジューリング問題や光ファイバーネットワーク の周波数割り当てに応用されている。

例

サイクルグラフでは、サイクルの長さが偶数の場合、辺を2色で塗ることができます。サイクルの周りで2色を交互に塗るだけです。ただし、長さが奇数の場合は、3色が必要です。^{[ 1 ]}

完全グラフK ₈の7辺彩色の幾何学的構成。7つの色クラスそれぞれには、中心から多角形の頂点への1辺と、それに垂直な3辺がある。

n頂点を持つ完全グラフ K n_は、 nが偶数のときn − 1色で辺彩色可能である。これはバラニャイの定理の特別な場合である。Soifer (2008) は、この場合の彩色の幾何学的構成を次のように示している。正( n − 1)辺を持つ多角形の頂点と中心にn点を配置する。各色クラスについて、中心から多角形の頂点の 1 つまでの辺と、多角形の頂点のペアを結ぶ垂直な辺をすべて含める。ただし、nが奇数のときはn色が必要である。各色は( n − 1)/2個の辺にしか使用できず、全体の1/ nの割合となる。 ^{[ 2 ]}

奇数グラフ、つまりn正則グラフの辺彩色については、これまで多くの研究者が研究を行ってきた。このグラフでは、頂点は2 n − 1人のプレイヤーから選ばれたn − 1人のプレイヤーからなるチームを表し、辺はこれらのチームの可能な組み合わせを表す（ただし、1 人のプレイヤーは「外れ」としてゲームを審判する）。n = 3の場合は、よく知られたピーターセン グラフとなる。Biggs (1972) が問題 ( n = 6の場合) を説明しているように、プレイヤーは、各チームが 6 試合をそれぞれ異なる曜日にプレイし、日曜日は全チームが休むような組み合わせのスケジュールを見つけたいと考えている。つまり、問題を数学的に定式化すると、6 正則奇数グラフO ₆の 6 辺彩色を見つけたいと考えていることになる。nが 3、4、または 8 の場合、O _nの辺彩色にはn + 1色が必要であるが、5、6、または 7 の場合はn色のみで済む。^{[ 3 ]}

定義

頂点彩色と同様に、グラフの辺彩色は、特に条件を付けずに言及される場合、常に辺の適切な彩色であるとみなされます。つまり、隣接する2つの辺に同じ色が割り当てられることはありません。ここで、2つの異なる辺は、共通の頂点を共有する場合に隣接しているとみなされます。グラフGの辺彩色は、線グラフ L ( G )の頂点彩色と同等であると考えることもできます。線グラフL ( G )は、 Gのすべての辺に頂点があり、 Gのすべての隣接する辺のペアに辺があります。

k つの異なる色による適切な辺彩色は、（適切な） k辺彩色と呼ばれます。 k辺彩色を割り当てることができるグラフは、 k辺彩色可能であると言われています。グラフGの（適切な）辺彩色に必要な最小の色の数は、彩色インデックス、または辺彩色数χ′( G )です。彩色インデックスは、 χ ₁ ( G )という表記法で書かれることもあります。この表記法で、添え字の 1 は、辺が 1 次元のオブジェクトであることを示します。グラフの彩色インデックスがちょうどkである場合、そのグラフはk辺彩色です。彩色インデックスは、 Gの適切な頂点彩色に必要な最小の色数である彩色数χ( G )またはχ ₀ ( G )と混同しないでください 。

特に断りのない限り、すべてのグラフは単純グラフであると仮定されます。これは、2つ以上の辺が同じ端点のペアを結んだり、自己ループが発生したりする可能性のある多重グラフとは対照的です。辺彩色に関する多くの問題において、単純グラフは多重グラフとは異なる振る舞いをするため、単純グラフの辺彩色に関する定理を多重グラフの場合に拡張するには、特別な注意が必要です。

マッチングとの関係

この3正則平面グラフは16個の頂点と24個の辺を持ちますが、最大マッチングでは7個の辺しか使えません。したがって、辺の色付けには4色が必要です

グラフGにおけるマッチングとは、どの2つの辺も隣接していない辺の集合です。完全マッチングとは、グラフのすべての頂点に接する辺を含むマッチングであり、最大マッチングとは、可能な限り多くの辺を含むマッチングです。辺彩色では、任意の色を持つ辺の集合はすべて互いに隣接していないため、マッチングを形成します。つまり、真辺彩色は、グラフを互いに素なマッチングに分割することと同じです。

与えられたグラフの最大マッチングのサイズが小さい場合、グラフのすべてのエッジをカバーするには多くのマッチングが必要になります。より正式に表現すると、この推論は、グラフに合計m個のエッジがあり、最大マッチングに属するエッジが最大β個である場合、グラフのすべてのエッジの色付けでは少なくともm /β 種類の異なる色を使用する必要があることを意味します。^{[ 4 ]}たとえば、図に示す 16 頂点の平面グラフにはm = 24個のエッジがあります。このグラフでは、完全なマッチングは存在できません。中心の頂点がマッチングすると、残りの一致しない頂点は 4 個、5 個、5 個の頂点を持つ 3 つの異なる接続コンポーネントにグループ化される可能性があり、頂点の数が奇数個のコンポーネントは完全に一致することができないためです。ただし、グラフには 7 個のエッジを持つ最大マッチングがあるため、β = 7です。したがって、グラフのエッジを色分けするために必要な色の数は少なくとも 24/7 であり、色の数は整数でなければならないため、少なくとも 4 色になります。

完全マッチングを持たないk次正則グラフの場合、この下限値を使用して、少なくともk + 1色が必要であることを示すことができます。^{[ 4 ]}特に、これは奇数個の頂点を持つ正則グラフ (奇完全グラフなど) に当てはまります。このようなグラフでは、ハンドシェイクの補題により、k自体が偶数でなければなりません。ただし、不等式χ′ ≥ m /β はすべての正則グラフの彩色指数を完全には説明しません。なぜなら、完全マッチングを持つもののk辺彩色可能ではない正則グラフが存在するからです。たとえば、ピーターセングラフはm = 15でβ = 5 の辺を持つ正則グラフであり、完全マッチングに 3 辺彩色はありません。

次数との関係

ヴィジングの定理

グラフGの辺彩色数は、最大次数Δ( G ) 、つまりGの任意の単一頂点に接続する辺の最大数と密接に関係しています。明らかに、χ′( G ) ≥ Δ( G )です。なぜなら、Δ 個の異なる辺がすべて同じ頂点vで交わる場合、これらの辺すべてに互いに異なる色を割り当てる必要があり、割り当て可能な色が少なくともΔ個ある場合にのみ可能だからです。 Vizing の定理( 1964 年に発表したVadim G. Vizingにちなんで名付けられました) によれば、この境界はほぼ厳密です。つまり、どのグラフでも、辺彩色数はΔ( G )またはΔ( G ) + 1 のいずれかです。χ′( G ) = Δ( G )の場合、G はクラス 1 であると言われ、それ以外の場合はクラス 2 であると言われます。

すべての二部グラフはクラス1である^{[ 5 ]。}また、ほぼすべてのランダムグラフはクラス1である^{[ 6 ]。}しかし、任意のグラフがクラス1であるかどうかを判断することはNP完全である^{[ 7 ]。}

Vizing (1965) は、最大次数が8以上の平面グラフはクラス1に属することを証明し、最大次数が7または6の平面グラフについても同様のことが成り立つと予想した。一方、最大次数が2から5までの平面グラフはクラス2に属する。この予想はその後、最大次数が7のグラフについても証明された。^{[ 8 ]}ブリッジレス平面立方グラフはすべてクラス1である。これは4色定理と同義である。^{[ 9 ]}

正則グラフ

k-正則グラフの1-因数分解、つまりグラフの辺を完全マ​​ッチングに分割することは、グラフのk-辺彩色と同じことです。つまり、正則グラフが1-因数分解を持つのは、クラス1の場合のみです。この特別なケースとして、立方体（3-正則）グラフの3-辺彩色は、テイト 彩色と呼ばれることがあります

すべての正則グラフが1-因数分解を持つわけではありません。例えば、ピーターセングラフは1-因数分解を持ちません。より一般的には、スナークグラフは、ピーターセングラフのように、ブリッジがなく、3-正則で、クラス2のグラフとして定義されます。

ケーニヒ（1916）の定理によれば、すべての二部正則グラフは1-因数分解を持つ。この定理は射影配置の観点から以前に述べられ、エルンスト・シュタイニッツによって証明された。

多重グラフ

次数6、辺多重度3のシャノン多重グラフ。任意の辺彩色に9色を必要とする

複数の平行辺が同じ2つの頂点を結ぶ マルチグラフについては、辺彩色数χ′( G )、最大次数Δ( G )、および多重度μ( G ) （任意の平行辺の束に含まれる辺の最大数）に関する、ヴィイジングの定理に類似するがそれよりも弱い結果が知られている。ヴィイジングの定理がマルチグラフに一般化されないことを示す簡単な例として、3つの頂点と、3組の頂点それぞれを結ぶ3つのμ( G )平行辺の束を持つマルチグラフであるシャノンマルチグラフを考える。この例では、Δ( G ) = 2μ( G ) （各頂点は 3 つのμ( G )本の平行エッジの束のうち 2 つにのみ接する）が、エッジ彩色数は3μ( G ) （合計3μ( G )本のエッジがあり、2 本すべてのエッジが隣接しているため、すべてのエッジに異なる色を割り当てる必要がある）である。 Vizing に影響を与えた結果として、^{[ 10 ]} Shannon (1949) は、これが最悪のケースであることを示した。任意のマルチグラフGについて、 χ′( G ) ≤ (3/2)Δ( G )。さらに、任意のマルチグラフGについて、χ′( G ) ≤ Δ( G ) + μ( G )であり、これは単純なグラフ（ μ( G ) = 1 ）の場合の Vizing の定理に帰着する不等式である。

アルゴリズム

グラフがクラス1であるかどうかを判定する問題はNP完全であるため、すべてのグラフを最適な色数で辺彩色する多項式時間アルゴリズムは知られていません。しかしながら、これらの基準の1つ以上を緩和するアルゴリズムがいくつか開発されています。これらのアルゴリズムは、グラフのサブセットのみで動作する、常に最適な色数を使用するわけではない、常に多項式時間で実行されるわけではない、といったものです。

特殊なグラフクラスの最適な色付け

最大次数Δの二部グラフまたは多重グラフの場合、最適な色の数はちょうどΔです。Cole 、Ost、Schirra (2001) は、これらのグラフの最適なエッジ彩色は、ほぼ線形の時間境界O( m log Δ)内で見つけられることを示し、ここでmはグラフのエッジの数です。より単純ですがいくぶん遅いアルゴリズムが、Cole & Hopcroft (1982)およびAlon (2003)によって説明されています。Alon (2003)のアルゴリズムは、二分割の同じ側に属する頂点のペアをマージし、次に少数の頂点とエッジを追加することで、次数を上げたりサイズを大幅に増やしたりすることなく、入力グラフを正則化することから始まります。次に、次数が奇数の場合、Alon はほぼ線形時間で 1 つの完全マッチングを見つけ、それに色を割り当ててグラフから削除し、次数を偶数にします。最後に、アロンは、グラフのオイラー巡回において辺の交互のサブセットを選択するとグラフが2つの正則サブグラフに分割されるというガボウ（1976）の観察を適用し、辺彩色問題を2つのより小さなサブ問題に分割します。そして、彼のアルゴリズムはこれらの2つのサブ問題を再帰的に解きます。彼のアルゴリズムの合計時間はO( m log m )です。

最大次数Δ ≥ 7の平面グラフの場合、最適な色数は再びΔとなる。Δ ≥ 9というより強い仮定を置くと、最適な辺彩色を線形時間で求めることができる（Cole & Kowalik 2008）。

隣接行列の2番目に大きい固有値（絶対値）が最大でd ^1−εであるという意味で擬似ランダムであるd-正則グラフの場合、dは最適な色数です（Ferber＆Jain 2020）。

最適な色数よりも多くの色を使用するアルゴリズム

Misra & Gries (1992)とGabow et al. (1985) は、Vizing の定理によって与えられた境界を満たす、任意のグラフをΔ + 1色で着色するための多項式時間アルゴリズムを説明しています。Misra & Gries のエッジ着色アルゴリズムを参照してください。

マルチグラフについては、Karloff & Shmoys (1987)がEli Upfalによる次のアルゴリズムを提示しています。入力マルチグラフGをオイラーグラフにするために、奇数次頂点すべてに辺で接続された新しい頂点を追加し、オイラー巡回を求め、巡回のための方向を選択します。有向巡回がG で u から v への辺を持つときはいつでも、二部グラフの左側の頂点 u から二部グラフの右側の頂点 v への辺を持ち、 Gの各頂点のコピーが二部グラフの各側に 1つずつ存在する二部グラフH を形成します。二部グラフの辺彩色アルゴリズムをHに適用します。 Hの各色クラスは、最大次数が 2 のサブグラフ、つまりパスとサイクルの互いに素な和集合を形成するGの辺の集合に対応します。そのため、Hの各色クラスに対して、 Gで 3 つの色クラスを形成することが可能です。アルゴリズムにかかる時間は、Cole、Ost & Schirra (2001)のアルゴリズムを使用して二部グラフの辺を色付けする時間O( m log Δ)によって制限される。このアルゴリズムが使用する色の数は最大で で、Shannon の境界 に近いが、完全に同じではない。また、簡単な方法で並列アルゴリズムにすることもできる。同じ論文で、Karloff と Shmoys は、同様の原理で動作する 4 色 (Shannon と Vizing の両方の境界に一致) で最大次数 3 のマルチグラフを色付けする線形時間アルゴリズムも提示している。彼らのアルゴリズムは、新しい頂点を追加してグラフをオイラーグラフにし、オイラー巡回を見つけ、次に巡回上で交互の辺セットを選択してグラフを最大次数 2 の 2 つのサブグラフに分割する。各サブグラフのパスとサイクルは、サブグラフごとに 2 色で色付けすることができる。このステップの後、残りの奇数サイクルにはそれぞれ、反対側のサブグラフに属する2色のいずれかで着色できる辺が少なくとも1つ含まれます。この辺を奇数サイクルから削除すると、そのサブグラフの2色で着色できるパスが残ります。 ${\displaystyle 3\left\lceil {\frac {\Delta}{2}}\right\rceil }$ ${\displaystyle \left\lfloor {\frac {3\Delta}{2}}\right\rfloor }$

グラフまたはマルチグラフのエッジを1つずつ考慮し、各エッジに最初に利用可能な色を割り当てる貪欲な彩色アルゴリズムは、2Δ − 1色もの色を使用することがあり、これは必要な色の数のほぼ2倍になる可能性があります。しかし、このアルゴリズムは、入力グラフが事前にわからないオンラインアルゴリズム設定で使用できるという利点があります。この設定では、その競合比は2であり、これは最適です。他のオンラインアルゴリズムはこれよりも優れたパフォーマンスを達成できません。^{[ 11 ]}ただし、エッジがランダムな順序で到着し、入力グラフの次数が少なくとも対数である場合、より小さな競合比を実現できます。^{[ 12 ]}

いくつかの著者は、任意のマルチグラフの分数彩色指数（線形計画法を用いて多項式時間で計算できる数）は彩色指数のいずれか1つ以内にあるという予想を立てている。^{[ 13 ]}これらの予想が正しいとすれば、マルチグラフの場合に彩色指数から1以上離れることのない数を計算できるようになり、これは単純なグラフに対するヴィイジングの定理で知られていることと一致する。一般には証明されていないが、これらの予想は彩色指数が少なくとも のときに成り立つことが知られており、これは十分に大きな多重度を持つマルチグラフで起こり得る。^{[ 14 ]}${\displaystyle \Delta +{\sqrt {\Delta /2}}}$

正確なアルゴリズム

グラフの辺を1色または2色で彩色できるかどうかをテストするのは簡単なので、辺彩色の最初の非自明なケースは、グラフに3辺彩色があるかどうかをテストすることです。Kowalik (2009)が示したように、多項式空間のみを使用して、グラフに3辺彩色があるかどうかをO(1.344 ⁿ )の時間でテストできます。この時間制限は指数関数的ですが、辺へのすべての可能な色の割り当てを力ずくで探索するよりも大幅に高速です。n頂点を持つすべての2連結3正則グラフには、O(2 n /2 ) の3辺彩色があります。これらはすべて^{、 O} ( 2 n /2 ) の時間でリストできます（^単一の彩色を見つける時間よりいくらか遅い）。グレッグ・クーパーバーグが指摘したように、 n /2辺の多角形上のプリズムのグラフはΩ(2 ^{n /2} )色付け（上限ではなく下限）を持ち、この境界が厳密であることを示している。^{[ 15 ]}

入力グラフの線グラフに頂点彩色の正確なアルゴリズムを適用することで、必要な色の数に関係なく、m辺を持つ任意のグラフを、 2 ^m m ^O(1)の時間で指数空間で、またはO(2.2461 ^m )の時間で多項式空間のみで最適に彩色することが可能です（Björklund、Husfeldt、Koivisto 2009）。

辺彩色は3色でもNP完全であるため、色数でパラメータ化された場合、固定パラメータでは扱いにくい可能性が高い。しかし、他のパラメータでは扱いやすい。特に、 Zhou、Nakano、Nishizeki (1996) は、木幅wのグラフに対して、最適な辺彩色をO( nw (6 w ) ^{w ( w + 1)/2} )の時間で計算できることを示した。この限界はwには超指数的に依存するが、グラフの頂点 数nには線形にしか依存しない。

Nemhauser & Park (1991) は、エッジカラーリング問題を整数計画問題として定式化し、整数計画ソルバーを用いてグラフのエッジカラーリングを行った経験について述べています。しかし、彼らはアルゴリズムの計算量解析を行っていません。

追加の特性

一意に3色に色付け可能な一般化ピーターセングラフG (9,2)。3つの色クラスのうち1つは明るい辺で示され、他の2つは明るい辺を各方向に40°回転するか、暗いハミルトンサイクルを交互の辺に分割することで見つけることができます

グラフが一意にk辺彩色可能であるとは、色のk !通りの順列を無視して、辺をk色のクラスに分割する方法が 1 つしかない場合である。 k ≠ 3の場合、一意にk辺彩色可能なグラフはパス、サイクル、スターのみであるが、k = 3の場合は他のグラフも一意にk辺彩色可能である可能性がある。一意に 3 辺彩色可能なグラフはすべて、ハミルトンサイクルを 3 つ(3 色のクラスのうち 1 つを削除することによって形成) 持つが、一般化ピーターセングラフG (6 n + 3, 2) ( n ≥ 2 ) のように、ハミルトンサイクルを 3 つ持ち、一意に 3 彩色可能ではない 3 正則グラフも存在する。唯一知られている非平面で一意に 3 彩色可能なグラフは一般化ピーターセングラフG (9,2)であり、他には存在しないと予想されている。^{[ 16 ]}

それぞれの色クラスが異なる直線上に平行線分として描かれた完全な二部グラフK _{3,3 。}

Folkman と Fulkerson (1969) は、与えられたグラフGの適切な辺彩色が存在し、その特性として、第 1 色の辺が_m 1個_、第2色の辺がm _2個、などとなるようなものが存在する、という非増加数列m 1 、 m 2 、 _{m 3}、…を調査した。彼らは、列P がこの意味で実行可能であり、辞書式順序で同じ和の列Qよりも大きい場合、 Q も実行可能であることを観察した。辞書式順序でP > Qであれば、各ステップで数m _iの 1 つを1 単位減らし、それ以降の数 m _j ( i < j ) を 1 単位増やすという一連のステップによって、 P をQに変換できる。辺彩色では、Pを実現する彩色から始めて、これらの同じステップのそれぞれを、 2 つの色を交互に繰り返す辺の最大パスであるKempe 連鎖上で色iとjを交換することによって実行できる。特に、どのグラフにも公平なエッジカラーリング、つまり 2 つのカラークラスのサイズが最大 1 単位だけ異なる最適な色の数を持つエッジカラーリングが存在します。

ド・ブリュイン・エルデシュ定理は、有限グラフの多くの辺彩色特性を無限グラフに応用するために用いることができる。例えば、グラフの次数とその彩色指数を関連付けるシャノンの定理とヴィジングの定理は、どちらも無限グラフに直接一般化できる。^{[ 17 ]}

Richter (2011) は、与えられた立方グラフのグラフ描画を見つける問題を考察している。このグラフ描画では、描画内の全ての辺が 3 つの異なる傾きのいずれかを持ち、かつ 2 つの辺が互いに同一線上にないという特性を持つ。このような描画が存在する場合、明らかに辺の傾きはグラフの 3 辺彩色で色として使用できる。例えば、ユーティリティ グラフK _3,3を正六角形の辺と長い対角線として描画することは、このようにグラフの 3 辺彩色を表す。Richter が示すように、与えられた Tait 彩色を持つ 3-正則単純二部グラフには、グラフが3 辺連結である場合に限り、与えられた彩色を表すこのタイプの描画が存在する。非二部グラフの場合、条件はもう少し複雑になります。与えられた彩色は、グラフの二部二重被覆が3辺連結であり、かつ単色辺のペアを削除しても非二部グラフとなる場合、描画によって表現できます。これらの条件はすべて多項式時間で簡単に検証できます。しかし、4辺彩色、4正則グラフに、4つの傾きを持つ辺を持つ描画（傾きで色を表す）が存在するかどうかを検証する問題は、実数の存在理論にとって完全であり、NP完全であることと少なくとも同程度に難しい 計算量クラスです。

グラフの最大次数や最大マッチング数に関係するだけでなく、彩度指数はグラフGの線型樹木度la( G )、つまりグラフの辺を分割できる線型フォレスト（パスの非結合和）の最小数にも密接に関係しています。マッチングは特別な種類の線型フォレストであり、逆に言えば、どの線型フォレストも 2 辺色にすることができるため、すべてのGについてla( G ) ≤ χ′( G ) ≤ 2 la( G )が成り立ちます。秋山予想（秋山仁にちなんで名付けられた）は と述べており、そこから2 la( G ) − 2 ≤ χ′( G ) ≤ 2 la( G )がより強く導かれます。最大次数3のグラフでは、la( G )は常にちょうど2なので、この場合、境界χ′( G )≤2la( G )はVizingの定理によって与えられた境界と一致する。^{[ 18 ]}${\displaystyle \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil }$

その他のタイプ

完全二部グラフK _4,4を3つの森に分割したもので、樹木度が3であることを示しています

グラフのThue数とは、すべての偶数長のパスにおいてパスの前半と後半が異なる色のシーケンスを形成するというより強い要件を満たすエッジカラーリングに必要な色の数です。

グラフの樹状性は、各色の辺が循環を持たない（標準的な辺彩色問題では、隣接する辺のペアが存在しない）ために必要な最小の色数である。つまり、グラフの辺を分割できる森の最小数である。 ^{[ 19 ]}彩色指数とは異なり、グラフの樹状性は多項式時間で計算できる。^{[ 20 ]}

リスト辺彩色は、各辺が色のリストに関連付けられたグラフが与えられ、各辺の色がその辺のリストから選択される適切な辺彩色を見つけなければならない問題である。グラフGのリスト彩色指数は、辺の色のリストをどのように選択したかに関係なく、各辺のリストに少なくともk色がある限り、彩色が可能であることが保証されるという特性を持つ最小の数 k である。したがって、リスト彩色指数は常に彩色指数以上の大きさである。部分ラテン方陣の完備化に関するディニッツ予想は、完全二部グラフK _n,nのリスト辺彩色数はその辺彩色数nに等しい、 という命題に言い換えることができる。Galvin (1995) は、より一般的には、すべての二部グラフにおいて彩色指数とリスト彩色指数が等しいことを証明することにより、この予想を解決した。彩色インデックスとリスト彩色インデックスの等式は、より一般的には、自己ループのない任意のマルチグラフに対しても成立すると推測されているが、この推測は未解決のままである。

頂点彩色の他の多くの一般的に研究されているバリエーションも、辺彩色に拡張されています。例えば、完全辺彩色は完全彩色の辺彩色版であり、各色のペアが少なくとも1組の隣接辺で表現され、色の総数を最大化することを目的とした適切な辺彩色です。^{[ 21 ]}強辺彩色は強彩色の辺彩色版であり、隣接する端点を持つ2つの辺はすべて異なる色を持つ必要があります。^{[ 22 ]}強辺彩色は、無線ネットワークのチャネル割り当て方式に応用されています。^{[ 23 ]}

非巡回辺彩色は、非巡回彩色の辺彩色の変形であり、2 つの色クラスすべてが非巡回部分グラフ (つまり、フォレスト) を形成する辺彩色です。^{[ 24 ]}グラフ の非巡回彩色指数 は、を適切に非巡回辺彩色するために必要な最小の色数です。 と予想されており、 はの最大次数です。^{[ 25 ]}現在知られている最良の境界は です。^{[ 26 ]}の内周が大きい場合、問題は容易になります。より具体的には、の内周が少なくとも である場合、となる定数があります。^{[ 27 ]}同様の結果から、すべての に対して が存在し、の内周が少なくとも である場合、 となります。^{[ 28 ]}${\displaystyle G}$ ${\displaystyle a'(G)}$ ${\displaystyle G}$ ${\displaystyle a'(G)\leq \Delta +2}$ ${\displaystyle \Delta }$ ${\displaystyle G}$ ${\displaystyle a'(G)\leq \lceil 3.74(\Delta -1)\rceil }$ ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle c\Delta \log \Delta }$ ${\displaystyle a'(G)\leq \Delta +2}$ ${\displaystyle \epsilon >0}$ ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle a'(G)\leq (1+\epsilon)\Delta }$

エップスタイン (2013)は、2つの二色閉路が互いに1つ以上の辺を共有しないという追加の特性を持つ立方体グラフの3辺彩色を研究した。彼は、このような彩色の存在は、辺が座標軸に平行で、各軸平行線が最大で2つの頂点を含む3次元整数グリッド上にグラフを描画することと同値であることを示した。しかし、標準的な3辺彩色問題と同様に、この種の彩色を求めることはNP完全である。

全彩色は、頂点と辺の両方を彩色する必要があるという点で、頂点彩色と辺彩色を組み合わせた彩色形式です。頂点と辺、または辺と辺の任意の隣接ペアは、隣接する2つの頂点と同様に、異なる色を持つ必要があります。ビジングの定理とブルックスの定理を組み合わせることで、任意のグラフには最大次数に2色を加えた数以下の全彩色が存在すると予想されていますが、これは未だ証明されていません。

曲面上の3次元正則グラフが3辺彩色されている場合、その双対グラフは、同様に辺彩色された（ただし、一般には正しく辺彩色されているわけではない）曲面の三角形分割を形成し、すべての三角形が各色の辺を1つずつ持つ。三角形分割のその他の彩色や向き、および三角形分割の頂点または面における色の配置に関する他の局所的制約は、いくつかの種類の幾何学的オブジェクトを符号化するために使用できる。例えば、長方形の細分（長方形の細分をさらに小さな長方形に分割し、各頂点で3つの長方形が交わる）は、「正則ラベル付け」、すなわち、その細分と双対な三角形分割の辺を2色彩色する手法によって組合せ的に記述できる。この場合、各頂点に接する辺は4つの連続する部分列を形成し、各部分列内の色は同じであるという制約が課される。このラベル付けは、長方形の細分化自体の色付けと双対であり、垂直の辺が1色、水平の辺が別の色になります。頂点の周囲に色付きの辺が現れる順序に関する同様の局所制約は、平面グラフや軸平行な辺を持つ3次元多面体の直線グリッド埋め込みをエンコードするためにも使用できます。これらの3種類の正規ラベル付けのそれぞれについて、固定グラフの正規ラベル付けの集合は分配格子を形成し、これを使用して同じグラフに基づくすべての幾何学的構造（たとえば、すべての軸平行多面体は同じ骨格を持つ）を迅速にリストしたり、追加の制約を満たす構造を見つけたりすることができます。^{[ 29 ]}

決定性有限オートマトンとは、各頂点が同じ出次数dを持ち、辺がd 色で彩色され、同じ始点を持つ2つの辺が異なる色を持つような有向グラフとして解釈できる。道路彩色問題とは、均一な出次数を持つ有向グラフの辺彩色において、結果のオートマトンが同期語 を持つように彩色する問題である。Trahtman (2009) は、与えられたグラフが強連結かつ非周期的である場合はいつでも、そのような彩色が存在することを証明することで、道路彩色問題を解決した。

ラムゼーの定理は、大きな完全グラフK _nの辺をk 色で彩色し、与えられたサイズ sの単色完全部分グラフK _sの生成を回避する問題に関するものである。この定理によれば、 n ≥ R ( s )の場合には、そのような彩色は不可能となるような数R _k ( s )が存在する。例えば、 R ₂ (3) = 6、つまりグラフK ₆の辺が2色であれば、常に単色三角形が存在する。

辺彩色グラフにおいて、パス上で同じ色が重複しない場合、そのパスはレインボーパスと呼ばれます。グラフは、任意の2つの頂点のペア間にレインボーパスが存在する場合、レインボーカラーと呼ばれます。グラフGの辺彩色を1. . . t 色で表す場合、すべての色が使用され、Gの各頂点に接続する辺の色がそれぞれ異なり、整数の区間を形成するとき、 t区間彩色と呼ばれます。

アプリケーション

完全グラフのエッジカラーリングは、ラウンドロビン方式のトーナメントをできるだけ少ないラウンド数に分割して、各ペアの競技者がいずれかのラウンドで対戦するようにスケジュールするために使用できます。このアプリケーションでは、グラフの頂点はトーナメントの競技者に、エッジはゲームに、エッジの色はゲームが行われるラウンドに対応します。 ^{[ 30 ]}同様のカラーリング手法は、全試合対戦ではない他のスポーツの組み合わせのスケジュールにも使用できます。たとえば、NFLでは、特定の年に対戦するチームのペアは、チームの前年の記録に基づいて決定され、次に、組み合わせのセットによって形成されたグラフにエッジカラーリングアルゴリズムが適用され、ゲームが行われる週末に割り当てられます。^{[ 31 ]}この応用では、ヴィイジングの定理によれば、どのような組み合わせを選んだとしても（同じシーズンに2回対戦するチームがない限り）、チームあたりの試合数よりも最大で1週末多く使うスケジュールを見つけることが常に可能である。

オープンショップスケジューリングは、製造するオブジェクトのセットがあり、各オブジェクトには（任意の順序で）実行されるタスクのセットがあり、各タスクは特定のマシンで実行され、同じマシンを必要とする他のタスクが同時に実行されないようにする生産プロセスのスケジュール設定の問題です。すべてのタスクの長さが同じである場合、この問題は、二部多重グラフの辺彩色の問題として形式化できます。二部多重グラフでは、二部分割の一方の頂点は製造するオブジェクトを表し、二部分割のもう一方の頂点は製造マシンを表し、辺は実行する必要があるタスクを表し、色は各タスクを実行できる時間ステップを表します。二部辺彩色は多項式時間で実行できるため、この制限されたオープンショップスケジューリングのケースでも同じことが当てはまります。^{[ 32 ]}

Gandham、Dawande、Prakash (2005) は、エッジカラーリングの変形として、センサーネットワーク上の時分割多元接続ネットワーク通信プロトコルのリンクスケジューリングの問題を研究しています。この問題では、無線通信ネットワークのエッジのタイムスロットを選択し、ネットワークの各ノードが干渉なく各隣接ノードと通信できるようにする必要があります。強力なエッジカラーリング (および各エッジカラーに 2 つのタイムスロット (各方向に 1 つ) を使用) を使用すると、問題は解決しますが、必要以上に多くのタイムスロットを使用する可能性があります。代わりに、彼らは、ネットワークの各無向エッジを 2 倍にして形成される有向グラフのカラーリングを求めています。このカラーリングでは、各有向エッジuvは、 vから出ているエッジおよびvの隣接エッジとは異なる色になります。彼らは、この問題に対するヒューリスティックとして、(Δ + 1)エッジカラーリングの分散アルゴリズムと、互いに干渉する可能性のあるエッジを再スケジュールする後処理フェーズを組み合わせて提案しています。

光ファイバー通信において、パス彩色問題は、相互に通信するノードのペアと、各ペアの光ファイバー通信ネットワーク上のパスに色（光の周波数）を割り当てる問題です。ただし、光ファイバーのセグメントを共有する2つのパスは、互いに同じ周波数を使用しないという制約があります。同じ通信スイッチを通過するが、光ファイバーのセグメントを経由しないパスは、同じ周波数を使用できます。通信ネットワークがスター型ネットワークとして構成され、単一の中央スイッチが各ノードに個別の光ファイバーで接続されている場合、パス彩色問題は、グラフまたはマルチグラフのエッジ彩色問題と全く同じモデル化できます。この場合、通信ノードがグラフの頂点、通信するノードのペアがグラフのエッジ、各ペアに使用できる周波数がエッジ彩色問題の色となります。より一般的なツリートポロジを持つ通信ネットワークの場合、ネットワーク内の各スイッチによって定義されるスター型ネットワークのローカルパス彩色ソリューションをパッチでつなぎ合わせて、単一のグローバルソリューションを形成できます。^{[ 33 ]}

未解決問題

ジェンセンとトフト（1995）は、辺彩色に関する23の未解決問題を挙げています。それらには以下が含まれます

• ゴールドバーグ (1973)の予想によれば、色指数と分数指数は互いに 1 つの範囲内にあり、これにより色指数を多項式時間で 1 つの色の範囲内で近似できることになります。
• ヤコブセンらによる、辺彩色における臨界グラフの構造に関するいくつかの予想。臨界グラフとは、任意の部分グラフの最大次数がより小さいか、クラス1であるようなクラス2のグラフのことである。ヤコブセンは当初、すべての臨界グラフの頂点数は奇数であると予想したが、これは最終的に反証された。この予想を弱める予想、あるいは臨界グラフおよび臨界多重グラフの頂点数を制限する予想は、未だにいくつか残されている。
• クラス 2 平面グラフで可能な最大次数を分類する Vizing の問題。
• AJW ヒルトンのオーバーフル サブグラフ予想では、次数がn /3以上のグラフはクラス 1 であるか、元のグラフと同じ次数Δで頂点の数が奇数kのサブグラフを含み、サブグラフの辺の数がΔ( k − 1)/2より大きいとされています。また、ハーバート グロッツシュとポール シーモアは、高次グラフの代わりに平面グラフに関する同様の予想をしています。
• アマンダ・チェトウィンドとアンソニー・ヒルトンの予想（おそらくガブリエル・アンドリュー・ディラックの研究に遡る）によると、頂点数が偶数nで次数が少なくともn /2である正則グラフはクラス 1 である。
• Claude BergeとDR Fulkersonの予想では、ブリッジのない 3 正則シンプル グラフのすべての辺を 2 倍にして形成される 6 正則マルチグラフは、6 色で辺色付けできる可能性があるとされています。
• フィオリーニとウィルソンの予想によれば、クローK _1,3以外の三角形のない平面グラフはすべて、一意に 3 辺色付け可能ではない。
• 2012年の予想では、Gがd-正則平面多重グラフであるとき、Gがd-辺彩色可能であることと、Gが奇数d-辺連結であることは同値である、とされている。この予想は、 d = 3のときに生じる4色定理の一般化である。マリア・チャドノフスキー、キャサリン・エドワーズ、ポール・シーモアは、8-正則平面多重グラフの辺彩色数は8であることを証明した。^{[ 34 ]}

注釈

1. Soifer (2008)、問題16.4、p.133
2. Soifer (2008)、問題16.5、p.133 n色または( n −1)色が必要であるという事実は、Vizingの定理の一例です
3. ビッグス（1972） ;メレディス＆ロイド（1973） ;ビッグス（1979） .
4. Soifer (2008)、134ページ。
5. ケーニヒ (1916)
6. エルデシュ＆ウィルソン（1977）。
7. ホリヤー（1981） .
8. サンダース＆チャオ（2001）。
9. テイト (1880) ;アペル＆ハーケン (1976)。
10. ソイファー（2008）、136頁。
11. Bar-Noy、Motwani、Naor (1992)。
12. バフマニ、メータ、モトワニ (2010)。
13. ゴールドバーグ（1973） ;アンダーセン（1977） ;シーモア（1979） .
14. チェン、ユー、ザン (2011)。
15. エップスタイン (2013) .
16. シュウェンク（1989） .
17. ボサック (1972) .
18. 秋山、エクソー、ハラリー (1980) ;ハビブとペローシュ (1982) ;ホラークとニーペル (1982)。
19. ナッシュウィリアムズ（1964年）。
20. ガボウ＆ウェスターマン（1992）。
21. ボザークとネシェトジル (1976)。
22. Fouquet & Jolivet (1983) ; Mahdian (2002) ; Frieze, Krivelevich & Sudakov (2005) ; Cranston (2006) .
23. バレットら（2006年）。
24. アロン、スダコフ、ザックス (2001) ;ムトゥ、ナラヤナン、スブラマニアン (2007)。
25. フィアムチク (1978) ;アロン、スダコフ、ザックス (2001)
26. Giotis et al. (2015) .
27. アロン、スダコフ、ザクス (2001)。
28. Cai et al. (2014) .
29. エップスタイン（2010） .
30. バーク、デ・ウェラ、キングストン (2004)。
31. スキエナ (2008) .
32. ウィリアムソンら（1997）。
33. エルレバッハ＆ヤンセン（2001）。
34. Chudnovsky、Edwards、Seymour (2015) .

参考文献

• 秋山 仁、エクソー ジェフリー、ハラリー フランク(1980)、「グラフの被覆とパッキング。III. 巡回的および非巡回的不変量」、Mathematica Slovaca、30 (4): 405– 417、MR  0595302。
• アロン、ノガ（2003）、「二部多重グラフの辺彩色のための簡単なアルゴリズム」、情報処理レター、85（6）：301-302、doi：10.1016/S0020-0190（02）00446-5、MR  1956451、S2CID  34965604。
• アロン、ノガ；スダコフ、ベニー；ザックス、アヤル（2001）「グラフの非巡回辺彩色」、Journal of Graph Theory、37（3）：157–167、doi：10.1002/jgt.1010、MR  1837021。
• Andersen, Lars Døvling (1977)、「グラフの辺着色について」、Mathematica Scandinavica、40 (2): 161– 175、doi : 10.7146/math.scand.a-11685、MR  0465922Chen, Yu & Zang (2011)より引用。
• アペル, K. ;ハケン, W. (1976)、「すべての平面写像は4色可能である」アメリカ数学会誌、82 (5): 711– 712、doi : 10.1090/S0002-9904-1976-14122-5、MR  0424602。
• Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010)、「ランダム順序到着モデルにおける1.43競合オンライングラフエッジ彩色アルゴリズム」、第21回ACM-SIAM離散アルゴリズムシンポジウム(SODA '10)の議事録、応用数学協会、pp.  31– 39、ISBN 9780898716986。
• Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992)、「貪欲アルゴリズムはオンラインエッジ彩色に最適である」、Information Processing Letters、44 (5): 251– 253、doi : 10.1016/0020-0190(92)90209-E。
• Barrett, CL; Istrate, G.; Kumar, VSA; Marathe, MV; Thite, S.; Thulasidasan, S. (2006)「無線ネットワークにおけるチャネル割り当てのための強力なエッジカラーリング」、Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006)、p. 106、doi : 10.1109/PERCOMW.2006.129、ISBN 0-7695-2520-2 S2CID  5797236。
• ビッグス、ノーマン（1972）、ガイ、リチャード・K.（編）、「辺彩色問題」、研究問題、アメリカ数学月刊、79（9）：1018–1020、doi：10.2307/2318076、JSTOR  2318076。
• ビッグス、ノーマン(1979)、「いくつかの奇グラフ理論」、第2回国際組合せ数学会議、ニューヨーク科学アカデミー紀要、319 (1): 71– 81、Bibcode : 1979NYASA.319...71B、doi : 10.1111/j.1749-6632.1979.tb32775.x、S2CID  84995087。
• ビョルクルンド、アンドレアス。ヒュースフェルト、トール。 Koivisto、Mikko (2009)、「包含-排他によるパーティショニングの設定」(PDF)、SIAM Journal on Computing、39 (2): 546–563、doi : 10.1137/070683933、MR  2529771。
• Bosák, Juraj (1972)、「有限グラフと無限グラフの彩色指数」、チェコスロバキア数学ジャーナル、22 (97): 272– 290、doi : 10.21136/CMJ.1972.101098、MR  0309777。
• ボサック、ジュラジ。Nešetřil、Jaroslav (1976)、「グラフの完全および疑似完全な色付け」、Matematicky Časopis Slovenskej Akadémie Vied、26 (3): 171–184、MR  0439672。
• Cai, XS; Perarnau, G.; Reed, BA ; Watts, AB (2014)「大きな内周を持つグラフの非巡回辺着色」、Random Structures & Algorithms、50 (4): 511– 533、arXiv : 1411.3047、doi : 10.1002/rsa.20695、S2CID  7727097。
• Burke, E.; De Werra, D.; Kingston, J. (2004)、「5.6.5 スポーツのタイムテーブル作成」、JL, Gross; Yellen, J. (編)、『グラフ理論ハンドブック』、CRC Press、p. 462、ISBN 978-1-58488-090-5。
• 陳 観涛；于 星星；尔 文南 (2011)、「多重グラフの彩色指数の近似」、Journal of Combinatorial Optimization、21 (2): 219– 246、doi : 10.1007/s10878-009-9232-y、MR  2770056、S2CID  169162。
• マリア・チュドノフスキー、キャサリン・エドワーズ、ポール・シーモア（2015年11月）「8正則平面グラフの辺彩色」、Journal of Combinatorial Theory、シリーズB、115 : 303– 338、arXiv : 1209.1176、doi : 10.1016/j.jctb.2015.05.002。
• コール、リチャード、ホップクロフト、ジョン（1982）、「二部グラフの辺彩色について」、SIAM Journal on Computing、11（3）：540–546、doi：10.1137/0211043、hdl：1813/6283、MR  0664720。
• コール、リチャード; コワリク、ウカス (2008)、「平面グラフの辺彩色のための新しい線形時間アルゴリズム」、アルゴリズミカ、50 (3): 351– 368、doi : 10.1007/s00453-007-9044-3、MR  2366985、S2CID  7692895。
• コール、リチャード; オスト、カースティン; シラー、ステファン (2001)、「O( E log D )時間での二部多重グラフの辺彩色」、コンビナトリカ、21 (1): 5– 12、doi : 10.1007/s004930170002、MR  1805711、S2CID  522145。
• クランストン、ダニエル W. (2006)、「22色を用いた最大次数4のグラフの強力なエッジカラーリング」、離散数学、306 (21): 2772– 2778、arXiv : math/0601623、Bibcode : 2006math......1623C、doi : 10.1016/j.disc.2006.03.053、MR  2264374、S2CID  1097275。
• エップスタイン、デイビッド（2013）、「曲げのない3次元直交グラフ描画の複雑性」、グラ​​フアルゴリズムとアプリケーションジャーナル、17（1）：35-55、arXiv：0709.4087、doi：10.7155/jgaa.00283、S2CID  2716392。
• Eppstein, David (2010)、「Regular labelings and geometric structures」、Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010) (PDF)、マニトバ大学、arXiv : 1007.0221、Bibcode : 2010arXiv1007.0221E。
• エルデシュ、ポール；ウィルソン、ロビン・J.（1977）「ほとんどすべてのグラフの彩色指数に関する注記」（PDF）、組合せ理論ジャーナル、シリーズB、23（2-3）：255-257、doi：10.1016/0095-8956（77）90039-9。
• エルレバッハ、トーマス、ヤンセン、クラウス（2001）、「パスカラーリングとコールスケジューリングの複雑性」、理論計算機科学、255（1-2）：33-50、doi：10.1016/S0304-3975(99)00152-8、MR  1819065。
• Ferber, Asaf; Jain, Vishesh (2020年9月)、「擬似ランダムグラフの1因数分解」、Random Structures & Algorithms、57 (2): 259– 278、arXiv : 1803.10361、doi : 10.1002/rsa.20927、S2CID  4680445。
• Fiamčik, J. ( 1978)、「グラフの非巡回彩色類」、Math. Slovaca、28 : 139–145。
• フィオリーニ、S.; ウィルソン、ロビン・ジェームズ (1977)、「グラフの辺彩色」、数学研究ノート、第16巻、ロンドン：ピットマン、ISBN 0-273-01129-4、MR  0543798。
• フォークマン、ジョン、フルカーソン、DR (1969)、「二部グラフの辺彩色」、組合せ数学とその応用（ノースカロライナ大学チャペルヒル校会議録、ノースカロライナ州チャペルヒル、1967年）、ノースカロライナ大学出版局、  561～ 577頁、MR  0262112。
• Fouquet, J.-L.; Jolivet, J.-L. (1983)、「グラフの強辺彩色と多重k角形への応用」、Ars Combinatoria、16 (A): 141– 150、MR  0737086。
• フリーズ、アラン・M. ; クリベレヴィッチ、マイケル; スダコフ、ベニー (2005)、「ランダムグラフの強い彩色指数」(PDF)、SIAM Journal on Discrete Mathematics、19 (3​​): 719–727 (電子版)、doi : 10.1137/S0895480104445757、MR  2191290。
• ガボウ、ハロルド・N.（1976）、「オイラー分割を用いた二部グラフのエッジカラー化」、国際コンピュータ情報科学ジャーナル、5（4）：345–355、doi：10.1007/BF00998632、MR  0422081、S2CID  36331285。
• ガボウ、ハロルド・N .；西関隆夫；カリフ、オデッド；レーベン、ダニエル；寺田修（1985）「グラフの辺彩色アルゴリズム」、技術報告書TRECIS-8501、東北大学。
• ガボウ、ハロルド・N. ; ウェスターマン、ハーバート・H. (1992)、「フォレスト、フレーム、ゲーム：マトロイド和とその応用のためのアルゴリズム」、アルゴリズミカ、7 ( 5– 6): 465– 497、doi : 10.1007/BF01758774、MR  1154585、S2CID  40358357。
• Galvin, F. (1995)、「二部多重グラフのリスト彩色指数」、Journal of Combinatorial Theory、シリーズB、63 (1): 153– 158、doi : 10.1006/jctb.1995.1011。
• Gandham, S.; Dawande, M.; Prakash, R. (2005)、「センサーネットワークにおけるリンクスケジューリング：分散エッジカラーリングの再考」、Proc. 24th INFOCOM、vol. 4、pp.  2492– 2501、doi : 10.1109/INFCOM.2005.1498534、ISBN 0-7803-8968-9、S2CID  8085139。
• Giotis, I.; Kirousis, L.; Psaromiligkos, KI; Thilikos, DM (2015)、「アルゴリズム的ロヴァース局所補題と非巡回辺彩色について」、解析アルゴリズムと組合せ論に関する第12回ワークショップ論文集 (ANALCO)、p. 16、doi : 10.1137/1.9781611973761.2、ISBN 978-1-61197-376-1。
• ゴールドバーグ、MK (1973)、「彩色指数がほぼ最大となるマルチグラフ」、ディスクレット分析(23): 3–7 , 72, MR  0354429Chen, Yu & Zang (2011)より引用。
• ハビブ, M.; ペロッシュ, B. (1982)、「線形樹状性に関するいくつかの問題」、離散数学、41 (2): 219– 220、doi : 10.1016/0012-365X(82)90209-6、MR  0676882。
• Holyer, Ian (1981)、「辺彩色のNP完全性」、SIAM Journal on Computing、10 (4): 718– 720、doi : 10.1137/0210055、S2CID  13131049。
• Horák, Peter; Niepel, Ľudovít (1982)、「立方グラフの線形樹状定理の簡潔な証明」、Acta Mathematica Universitatis Comenianae、40/41: 275–277、MR  0686983。
• ジェンセン、トミー・R.; トフト、ビャーネ（1995年）、グラフカラーリング問題、ニューヨーク：ワイリー・インターサイエンス、ISBN 0-471-02865-7。
• カーロフ、ハワード・J.；シュモイズ、デビッド・B.（1987）、「辺彩色問題のための効率的な並列アルゴリズム」、Journal of Algorithms、8（1）：39–52、doi：10.1016/0196-6774(87)90026-5、MR  0875324。
• Kőnig, D. (1916)、「Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre」、Mathematische Annalen、77 (4): 453–465、doi : 10.1007/BF01456961、hdl : 10338.dmlcz/127635、S2CID  121097364、オリジナルから2015-01-19 にアーカイブされ、2013-09-30 に取得。
• Kowalik, Łukasz (2009)、「3色によるエッジカラーリングの改良」、理論計算機科学、410 ( 38– 40): 3733– 3742、doi : 10.1016/j.tcs.2009.05.005、MR  2553326。
• マディアン、モハマド（2002）「強辺彩色の計算複雑性について」離散応用数学、118（3）：239–248、doi：10.1016/S0166-218X（01）00237-2、MR  1892971。
• メレディス、ガイ・HJ; ロイド、E. キース (1973)、「クロームのフットボール選手たち」、コンビナトリアル理論ジャーナル、シリーズB、15 (2): 161– 166、doi : 10.1016/0095-8956(73)90016-6。
• ミスラ, J.;グリース, デイヴィッド(1992)、「ヴィジングの定理の構成的証明」、情報処理レター、41 (3): 131– 133、doi : 10.1016/0020-0190(92)90041-S。
• Muthu, Rahul; Narayanan, N.; Subramanian, CR (2007)、「非巡回エッジ着色の改良境界」、離散数学、307 (23): 3063– 3069、doi : 10.1016/j.disc.2007.03.006、MR  2371078。
• ナッシュ＝ウィリアムズ、C. St. JA ( 1964)、「有限グラフの森への分解」、ロンドン数学会誌、第2シリーズ、39 :12、doi : 10.1112/jlms/s1-39.1.12、MR0161333 
• ネムハウザー、ジョージ・L. ; パーク、ソンス (1991)、「エッジカラーリングへの多面体アプローチ」、オペレーションズ・リサーチ・レターズ、10 (6): 315– 322、doi : 10.1016/0167-6377(91)90003-8、MR  1128970。
• Richter, David A. (2011), 「Tait-colorableグラフの描き方」, Brandes, Ulrik ; Cornelsen, Sabine (eds.), Proc. 18th International Symposium on Graph Drawing (GD 2010) , Lecture Notes in Computer Science, vol. 6502, Springer-Verlag, pp.  353– 364, doi : 10.1007/978-3-642-18469-7_32 , ISBN 978-3-642-18468-0。
• サンダース、ダニエル・P .；チャオ、ユエ（2001）「最大次数7の平面グラフはクラスIである」、Journal of Combinatorial Theory、シリーズB、83（2）：201–212、doi：10.1006/jctb.2001.2047。
• シーモア, PD (1979)、「立方グラフの多色化とフルカーソンとタットの予想について」、ロンドン数学会紀要、第3シリーズ、38 (3): 423– 460、doi : 10.1112/plms/s3-38.3.423、MR  0532981。
• シュウェンク、アレン・J.（1989）「ある一般化ピーターセングラフにおけるハミルトンサイクルの列挙」、Journal of Combinatorial Theory、シリーズB、47（1）：53-59、doi：10.1016/0095-8956（89）90064-6、MR  1007713。
• シャノン、クロード・E. (1949)、「ネットワークの線の色付けに関する定理」、J. Math. Physics、28 ( 1– 4): 148– 151、doi : 10.1002/sapm1949281148、hdl : 10338.dmlcz/101098、MR  0030203。
• スキエナ、スティーブン・S. (2008)、「16.8 エッジカラーリング」、アルゴリズム設計マニュアル（第2版）、シュプリンガー・フェアラーク、pp.  548– 550、doi : 10.1007/978-1-84800-070-4_16、ISBN 978-1-84800-069-8ストーニーブルック・アルゴリズム・リポジトリにある本書のこのセクションのウェブサイトも参照してください
• ソイファー、アレクサンダー（2008年）、数学カラーリングブック、シュプリンガー・フェアラーク、ISBN 978-0-387-74640-1。
• テイト、PG（1880）、「地図の色彩に関する考察」、Proc. R. Soc. Edinburgh、10 : 729、doi : 10.1017/S0370164600044643。
• トラハトマン、アヴラハム・N.（2009）「道路の色分け問題」、イスラエル数学ジャーナル、172（1）：51– 60、arXiv：0709.0099、doi：10.1007/s11856-009-0062-5、S2CID  515742。
• Vizing, VG (1964)「 pグラフの彩度クラスの推定について」、Diskret. Analiz.、3 : 25–30、MR  0180505。
• Vizing, VG (1965)「与えられた彩色クラスを持つ臨界グラフ」Metody Diskret. Analiz . 5 : 9– 17（ロシア語）
• Williamson, DP ; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997)、「ショートショップスケジュール」、オペレーションズ・リサーチ、45 (2): 288– 294、doi : 10.1287/opre.45.2.288、JSTOR  171745、MR  1644998。
• 周暁; 中野真一; 西関隆夫(1996)「エッジカラーリング部分k木」, Journal of Algorithms , 21 (3): 598– 617, doi : 10.1006/jagm.1996.0061 , MR  1417666。