色彩の区別

すべての対称性を破壊するグラフ頂点への色の割り当て

グラフ理論において、グラフの識別彩色または識別ラベル付けとは、グラフの頂点に色またはラベルを割り当てることで、グラフの非自明な対称性をすべて破壊することである。この彩色は適切な彩色である必要はなく、隣接する頂点に同じ色を割り当てることも可能である。彩色されたグラフでは、隣接性と彩色の両方を維持するような、頂点同士の一対一の対応関係は存在しない。識別彩色における最小の色数は、グラフの 識別数と呼ばれる。

識別色と識別数は、アルバートソンとコリンズ（1996）によって導入されました。彼らは、フランク・ルービンが以前に考案したパズルに基づいて、次のような動機づけとなる例を示しました。「異なるドアへの鍵の輪があるとします。それぞれの鍵は1つのドアしか開けませんが、どれも区別がつきません。各鍵を一意に識別できるように、鍵のハンドルを色分けするには、何色必要でしょうか？」^{[1]この例は、}循環グラフの識別色を用いて解かれます。このような色分けにより、各鍵は、その色とそれを囲む色の順序によって一意に識別されます。^[2]

例

8 つの非対称グラフ。それぞれ 1 色 (赤) のみで区別する色分けが与えられています。

グラフが識別番号1を持つのは、それが非対称である場合に限ります。^[3]たとえば、Fruchtグラフは1色のみで識別色付けされます。

完全グラフでは、各頂点に異なる色を割り当てることのみが識別彩色である。なぜなら、2つの頂点に同じ色が割り当てられた場合、それらの2つの頂点を入れ替え、残りの頂点はそのままにする対称性が存在するからである。したがって、完全グラフ $K n$ $の識別数はn$ である。しかし、 $K$ $n$ の各頂点に次数1の頂点を接続することで $K n$ から得られるグラフは、同じ対称群を持つにもかかわらず、識別数が大幅に小さくなる。このグラフは、頂点 $K$ $n$ とその隣接する頂点の各ペアに異なる色の順序付きペアを使用することで得られる色による識別彩色を持つ。^[2] $\lceil {\sqrt {n}}\rceil$

3、4、または 5 つの頂点を持つサイクルグラフの場合、識別カラーリングを構成するには 3 色が必要です。たとえば、5 つのサイクルのすべての 2 カラーリングには、反射対称性があります。これらのサイクルのそれぞれで、隣接する 2 つの頂点にそれぞれ一意の色を割り当て、残りのすべての頂点に 3 番目の色を使用すると、3 色の識別カラーリングが得られます。ただし、6 つ以上の頂点を持つサイクルでは、2 色のみで識別カラーリングができます。つまり、Frank Rubin のキーリングパズルでは、3、4、または 5 つのキーのリングには 3 色が必要ですが、6 つ以上のキーまたは 2 つのキーの場合は 2 色のみが必要です。^[2]たとえば、示されている 6 つのキーのリングでは、各キーはその色と、隣接する反対色のキーのブロックの長さで区別できます。キーの色と隣接ブロックの長さの組み合わせごとに、キーは 1 つだけです。

超立方体グラフはサイクルグラフと同様の現象を示す。2次元および3次元の超立方体グラフ（それぞれ4次元サイクルと立方体のグラフ）の識別数は3である。しかし、より高次元の超立方体グラフの識別数は2のみである。^[4]

ピーターセングラフの識別数は3です。しかし、このグラフと完全グラフ以外のすべてのクネザーグラフの識別数は2です。^[5]同様に、一般化されたピーターセングラフの中では、ピーターセングラフ自体と立方体のグラフだけが識別数が3で、残りは識別数が2です。^[6]

計算の複雑さ

木、平面グラフ、区間グラフの識別数は多項式時間で計算できる。^[7]^[8]^[9]

識別数の計算の正確な複雑さは不明である。これは、未だ解明されていないグラフ同型性の複雑さと密接に関連しているからである。しかしながら、これは複雑さのクラス AMに属することが示されている。^[10]さらに、識別彩色数が最大で3であるかどうかをテストすることはNP困難であり、^[9]識別彩色数が最大で2であるかどうかをテストすることは「少なくともグラフ自己同型性と同じくらい難しいが、グラフ同型性ほど難しくはない」。^[11]

追加のプロパティ

与えられたグラフの色付けが、そのグラフにとって識別的であるのは、補グラフにとって識別的である場合に限ります。したがって、すべてのグラフは、その補グラフと同じ識別数を持ちます。^[2]

任意のグラフ $Gについて、$ $G$ の識別数は最大で $G$ の自己同型数の対数に比例する。自己同型が非自明なアーベル群を形成する場合、識別数は2であり、二面体群を形成する場合、識別数は最大で3である。^[2]

あらゆる有限群に対して、その群を自己同型群とし、区別数が2であるグラフが存在する。^[2]この結果は、あらゆる有限群はグラフの対称群として実現できるというフルクトの定理を拡張したものである。

バリエーション

適切な弁別彩色とは、弁別彩色でありながら適切な彩色でもある場合である。すなわち、隣接する2つの頂点はそれぞれ異なる色を持つ。グラフの適切な弁別彩色における最小の色数は、そのグラフの弁別彩色数と呼ばれる。^[12]

参考文献

^ ルービン、フランク（1979）、「問題729：盲人の鍵」、レクリエーション数学ジャーナル、11：1281980年第12巻の解答。Albertson & Collins (1996) が引用。Rubin は色を使う代わりに、触覚で互いに区別できる鍵のハンドルという概念を用いて問題を表現した。より正確には、この問題では各鍵が対称形であると仮定しており、鍵ホルダー上の向きでは鍵を区別できない。
^ abcdef Albertson, Michael O.; Collins, Karen L. (1996)、「グラフにおける対称性の破れ」、Electronic Journal of Combinatorics、3 (1): R18、doi : 10.37236/1242、MR 1394549。
^ 例えば、Imrich, Wilfried; Klavžar, Sandi (2006)、「グラフのカルテシアンべき乗の区別」、Journal of Graph Theory、53 (3): 250– 260、CiteSeerX 10.1.1.59.9242、doi :10.1002/jgt.20190、MR 2262268、S2CID 6808067を参照。グラフに非自明な自己同型がない場合、その識別数は 1 です。言い換えると、非対称グラフの場合、 $D$ $($ $G$ $) = 1 です。$
^ ボグスタッド、ビル、コーウェン、レノア・J. (2004)、「超立方体の識別数」、離散数学、283 ( 1–3 ): 29– 35、doi : 10.1016/j.disc.2003.11.018、MR 2061481。
^ Albertson, Michael O.; Boutin, Debra L. (2007)、「決定集合を用いたKneserグラフの識別」、Electronic Journal of Combinatorics、14 (1): R20、doi : 10.37236/938、MR 2285824。
^ Lal, AK; Bhattacharjya, B. (2009)、「ブックグラフと一般化ピーターセングラフの対称性の破壊」、SIAM Journal on Discrete Mathematics、23 (3): 1200– 1216、doi :10.1137/080728640、MR 2538646 LalとBhattacharjya（定理4.3）は、この結果をKS Potanka（バージニア工科大学、1998年）の未発表の修士論文によるものとしている。
^ Cheng, Christine T. (2006)、「木と森の識別数の計算について」、Electronic Journal of Combinatorics、13 (1): R11、doi : 10.37236/1037、MR 2200539。
^ Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R. (2008)、「平面グラフの識別数の計算とその先：計数アプローチ」、SIAM Journal on Discrete Mathematics、22 (4): 1297– 1324、arXiv : math/0703927、doi :10.1137/07068686X、MR 2443115、S2CID 2402306 。
^ ab Cheng, Christine T. (2009)、「区間グラフの識別彩色数と識別彩色数の計算およびその他の結果について」、離散数学、309 (16): 5169– 5182、doi : 10.1016/j.disc.2009.04.004、MR 2548918。
^ ラッセル、アレクサンダー、スンダラム、ラヴィ（1998）、「グラフ識別可能性の漸近論と計算複雑性に関する注記」、Electronic Journal of Combinatorics、5：R23、doi：10.37236/1361、MR 1617449。
^ Eschen, Elaine M.; Hoàng, Chính T.; Sritharan, R.; Stewart, Lorna (2011)「グラフの識別彩色数が最大で2であるかどうかを判断する複雑さについて」、Discrete Mathematics、311 (6): 431– 434、arXiv : 0907.0691、doi :10.1016/j.disc.2010.12.013、MR 2799894、S2CID 7679211 。
^ コリンズ、カレン・L. ;トレンク、アン・N. (2006)、「識別彩色数」、電子ジャーナル・オブ・コンビナトリクス、13 (1): R16、doi : 10.37236/1042、MR 2200544 。

[1] ルービン、フランク（1979）、「問題729：盲人の鍵」、レクリエーション数学ジャーナル、11：1281980年第12巻の解答。Albertson & Collins (1996) が引用。Rubin は色を使う代わりに、触覚で互いに区別できる鍵のハンドルという概念を用いて問題を表現した。より正確には、この問題では各鍵が対称形であると仮定しており、鍵ホルダー上の向きでは鍵を区別できない。

[ac-2] Albertson, Michael O.; Collins, Karen L. (1996)、「グラフにおける対称性の破れ」、Electronic Journal of Combinatorics、3 (1): R18、doi : 10.37236/1242、MR 1394549。

[3] 例えば、Imrich, Wilfried; Klavžar, Sandi (2006)、「グラフのカルテシアンべき乗の区別」、Journal of Graph Theory、53 (3): 250– 260、CiteSeerX 10.1.1.59.9242、doi :10.1002/jgt.20190、MR 2262268、S2CID 6808067を参照。グラフに非自明な自己同型がない場合、その識別数は 1 です。言い換えると、非対称グラフの場合、 $D$ $($ $G$ $) = 1 です。$

[4] ボグスタッド、ビル、コーウェン、レノア・J. (2004)、「超立方体の識別数」、離散数学、283 ( 1–3 ): 29– 35、doi : 10.1016/j.disc.2003.11.018、MR 2061481。

[5] Albertson, Michael O.; Boutin, Debra L. (2007)、「決定集合を用いたKneserグラフの識別」、Electronic Journal of Combinatorics、14 (1): R20、doi : 10.37236/938、MR 2285824。

[6] Lal, AK; Bhattacharjya, B. (2009)、「ブックグラフと一般化ピーターセングラフの対称性の破壊」、SIAM Journal on Discrete Mathematics、23 (3): 1200– 1216、doi :10.1137/080728640、MR 2538646 LalとBhattacharjya（定理4.3）は、この結果をKS Potanka（バージニア工科大学、1998年）の未発表の修士論文によるものとしている。

[7] Cheng, Christine T. (2006)、「木と森の識別数の計算について」、Electronic Journal of Combinatorics、13 (1): R11、doi : 10.37236/1037、MR 2200539。

[8] Arvind, V.; Cheng, Christine T.; Devanur, Nikhil R. (2008)、「平面グラフの識別数の計算とその先：計数アプローチ」、SIAM Journal on Discrete Mathematics、22 (4): 1297– 1324、arXiv : math/0703927、doi :10.1137/07068686X、MR 2443115、S2CID 2402306 。

[c09-9] Cheng, Christine T. (2009)、「区間グラフの識別彩色数と識別彩色数の計算およびその他の結果について」、離散数学、309 (16): 5169– 5182、doi : 10.1016/j.disc.2009.04.004、MR 2548918。

[10] ラッセル、アレクサンダー、スンダラム、ラヴィ（1998）、「グラフ識別可能性の漸近論と計算複雑性に関する注記」、Electronic Journal of Combinatorics、5：R23、doi：10.37236/1361、MR 1617449。

[11] Eschen, Elaine M.; Hoàng, Chính T.; Sritharan, R.; Stewart, Lorna (2011)「グラフの識別彩色数が最大で2であるかどうかを判断する複雑さについて」、Discrete Mathematics、311 (6): 431– 434、arXiv : 0907.0691、doi :10.1016/j.disc.2010.12.013、MR 2799894、S2CID 7679211 。

[12] コリンズ、カレン・L. ;トレンク、アン・N. (2006)、「識別彩色数」、電子ジャーナル・オブ・コンビナトリクス、13 (1): R16、doi : 10.37236/1042、MR 2200544 。