エッジカラーリング

グラフ理論では、グラフの適切な辺彩色とは、2 つの入射辺が同じ色にならないようにグラフの辺に「色」を割り当てることです。たとえば、右の図は、赤、青、緑の色によるグラフの辺彩色を示しています。辺彩色は、グラフ彩色のいくつかの異なるタイプの 1 つです。辺彩色問題は、kの値が与えられた場合に、最大k 個の異なる色を使用して、または可能な限り少ない色を使用して、与えられたグラフの辺を彩色できるかどうかを尋ねます。与えられたグラフの辺に必要な色の最小数は、グラフの彩度指数と呼ばれます。たとえば、図のグラフの辺は 3 色で彩色できますが、2 色で彩色することはできないため、示されているグラフの彩度指数は 3 です。

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

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

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

奇数グラフの辺彩色については、複数の著者が研究している。奇数グラフは、頂点が2 n − 1 人のプレイヤーのプールから選ばれたn − 1人のプレイヤーのチームを表し、辺がこれらのチームの可能な組み合わせを表す n 正則グラフである (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 つ以上のエッジが同じエンドポイントのペアを接続し、自己ループが存在する可能性があるマルチグラフとは対照的です。エッジカラーリングの多くの問題では、単純グラフはマルチグラフとは異なる動作をするため、単純グラフのエッジカラーリングに関する定理をマルチグラフのケースに拡張するには追加の注意が必要です。

グラフGのマッチングは、どの 2 つのエッジも隣接していないエッジの集合です。完全マッチングは、グラフのすべての頂点に接するエッジを含むマッチングであり、最大マッチングは、可能な限り多くのエッジを含むマッチングです。エッジ カラーリングでは、任意の 1 つの色を持つエッジの集合はすべて互いに隣接していない必要があるため、マッチングを形成します。つまり、適切なエッジ カラーリングは、グラフを互いに素なマッチングに分割することと同じです。

与えられたグラフの最大マッチングのサイズが小さい場合、グラフのすべてのエッジをカバーするには多くのマッチングが必要になります。より正式に表現すると、この推論は、グラフに合計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 辺彩色は、Tait 彩色と呼ばれることがあります。

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

Kőnig (1916) の定理によれば、すべての二部正則グラフには 1 因数分解があります。この定理は以前に射影構成の観点から述べられ、 Ernst Steinitzによって証明されました。

複数の平行辺が同じ 2 つの頂点を接続する可能性があるマルチグラフについては、辺彩色数 χ′( G )、最大次数Δ( G )、および多重度μ( G ) (任意の平行辺の束の最大辺数) に関する、Vizing の定理に似ているがより弱い結果が知られています。Vizing の定理がマルチグラフに一般化されないことを示す簡単な例として、3 つの頂点と、3 組の頂点のそれぞれを接続する 3 つのμ( G )平行辺の束を持つマルチグラフであるShannon マルチグラフを考えます。この例では、Δ( 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 はほぼ線形時間で単一の完全マッチングを見つけ、それに色を割り当ててグラフから削除し、次数を偶数にします。最後に、アロンは、グラフのオイラーツアーでエッジの交互のサブセットを選択すると、グラフが 2 つの通常のサブグラフに分割されるという Gabow (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の各頂点のコピーが 2 つ(二分割の各側に 1 つ)あり、有向巡回が G でuからv への辺を持つときはいつでも、二分割の左側の頂点 u から二分割の右側の頂点 vへの辺を持つ、二部グラフHを形成します。二部グラフの辺色付けアルゴリズムをHに適用します。 Hの各色クラスは、最大次数 2 のサブグラフ、つまりパスとサイクルの互いに素な和集合を形成するGの辺の集合に対応します。そのため、Hの各色クラスに対して、 Gで 3 つの色クラスを形成することが可能です。アルゴリズムの所要時間は、Cole、Ost & Schirra (2001) のアルゴリズムを使用して二部グラフの辺に色を付ける時間O( m log Δ)によって制限される。このアルゴリズムが使用する色の数は最大で で、Shannon の の制限に近いが、完全に同じではない。また、簡単な方法で並列アルゴリズムにすることもできる。同じ論文で、Karloff と Shmoys は、最大次数 3 のマルチグラフを 4 色で色付けする線形時間アルゴリズムも提示している (Shannon と Vizing の両方の制限に一致)。このアルゴリズムは、同様の原理で動作する。彼らのアルゴリズムは、新しい頂点を追加してグラフをオイラーグラフにし、オイラー巡回を見つけ、巡回上の交互の辺セットを選択して、グラフを最大次数 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倍である2Δ − 1色も使用することがあります。ただし、入力グラフが事前にわからないオンラインアルゴリズム設定で使用できるという利点があります。この設定では、競合比は2であり、これは最適です。他のオンラインアルゴリズムでは、これよりも優れたパフォーマンスを達成できません。^[11]ただし、エッジがランダムな順序で到着し、入力グラフの次数が少なくとも対数である場合、より小さな競合比を実現できます。^[12]

複数の著者が、任意のマルチグラフの分数彩色指数（線形計画法を用いて多項式時間で計算できる数）は彩色指数の 1 つ以内にあるという予想を立てている。^[13]これらの予想が正しい場合、マルチグラフの場合に彩色指数から 1 以内の数値を計算できるようになり、単純なグラフに対する Vizing の定理で知られているものと一致する。一般には証明されていないが、これらの予想は彩色指数が 以上のときに成り立つことが知られており、これは十分に大きな多重度を持つマルチグラフで起こり得る。^[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 ) の時間でリストできます(^単一の着色を見つける時間よりいくらか遅い)。Greg Kuperbergが観察したように、 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) は、エッジカラーリング問題を整数計画法として定式化し、整数計画法ソルバーを使用してグラフのエッジカラーリングを行った経験について説明しています。ただし、彼らはアルゴリズムの複雑さの分析は行っていません。

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

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

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

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

グラフの最大次数と最大マッチング数に関係するのと同様に、彩度指数はグラフGの線形樹状度 la( 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 }$

グラフの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 }$

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

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

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

決定性有限オートマトンとは、各頂点が同じ出次数d を持ち、同じソース頂点を持つ 2 つの辺がすべて異なる色になるように辺がd色付けされる有向グラフとして解釈できます。道路色付け問題は、結果のオートマトンが同期ワードを持つように、均一な出次数を持つ有向グラフの辺色付けを行う問題です。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週末多く使用するスケジュールを見つけることが常に可能であることを意味しています。

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

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

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

Jensen & Toft (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]