区間エッジカラーリング
Coloring in which edges are labeled by integers

グラフ理論において、区間エッジ彩色は、ある区間内の整数によってエッジがラベル付けされ、その区間内のすべての整数が少なくとも 1 つのエッジで使用され、各頂点で接続エッジに現れるラベルが異なる数字の連続したセットを形成するタイプのエッジ彩色です。

歴史

連続辺彩色の概念は、1987年にAsratianとKamalianが論文「多重グラフの辺の区間彩色」の中で「区間辺彩色」という用語とともに導入した。 [1]グラフの区間辺彩色が導入されて以来、すべてのグラフが区間辺彩色できるわけではないため、数学者は区間辺彩色可能なグラフの存在を調査してきた。区間辺彩色を可能にする単純なグラフ族は偶数次完全グラフであり、グラフ族の反例として奇数次完全グラフがある。区間彩色できない最小のグラフ。Sevast'janovによって発見された、区間彩色できない頂点数28個、最大次数21のグラフもあるが、最大次数が4から12の間であるグラフの区間彩色可能性はまだ不明である。

AsratyanとKamalyan（1987）は、グラフが区間彩色可能である場合、辺彩色数は頂点数より1小さいか等しいことを証明し、また、Gがr-正則グラフである場合、Gが適切なr-辺彩色を持つ場合のみ、Gは区間彩色を持つことを指摘した。[1]

区間エッジ彩色は、正規グラフ、正規および非正規の二部グラフ、平面グラフ、区間エッジ彩色で開始されたその他の拡張などで調査されます。

意味

G を単純な区間グラフとする。グラフ G の辺彩色を色 1, 2, . . . , tで表すと、各i ∈ {1, 2, . . . , t } に対して、少なくとも 1 つの辺がiで彩色され、 Gの任意の頂点に接続する辺の色が異なり、整数の区間を形成する場合、「区間t彩色」と呼ばれる。[2]あるいは、区間辺彩色は次のように定義される。グラフGの辺彩色を色 1. . . tで表すと、すべての色が使用され、 Gの各頂点に接続する辺の色が異なり、整数の区間を形成する場合、「区間 t 彩色」と呼ばれる。グラフGが「区間彩色可能」であるとは、 G が何らかの正の整数tに対して区間 t 彩色を持つ場合である。区間彩色可能なすべてのグラフの集合をNとする。グラフG ∈ Nにおいて、 Gが区間t彩色を持つ場合のtの最小値と最大値は、それぞれw ( G ) とW ( G )で表される。グラフの区間辺彩色は、グラフの任意の2つの色クラスの差が最大でも1である場合、公平区間辺彩色と呼ばれる。

頂点 (x) に接続する辺の色の集合は、( x ) のスペクトルと呼ばれます。G の頂点の部分集合Rがi特性を持つとは、 R上の区間となるGの適切な辺t彩色が存在することを意味します。

いくつかの結果

三角形のないグラフG=(V,E)が区間t彩色を持つ場合、t ≤ |V|−1となる。AsratyanとKamalianは、Gが区間彩色可能であればχ'(G)=∆(G)となることを証明した。 [1] [3]

Petrosyan は、完全グラフと n 次元立方体の区間彩色を調査し、n ≤ t ≤ n(n+1)/2 の場合、n 次元立方体 Qn は区間 t 彩色を持つことを示しました。[2] Axenovich は、3 つ以上の頂点があり、三角形を分離しないすべての外平面三角形分割は区間彩色可能であることを証明しました。[4] Gが正則グラフ w(G)=∆(G) で あり、G がすべての t に対して区間 t 彩色を持つ場合、w(G) ≤ t ≤ W(G) となります。

K 6の区間5色

完全グラフの区間辺彩色[2]

  • 完全グラフは、その頂点の数が偶数の場合に限り、区間彩色可能です。
  • n= p 2 q（pは奇数、qは非負、2n−1≤t≤4n−2−p−q）の場合、完全グラフK 2nには区間t色付けがあります。
  • Fが完全グラフK2n +1の1つの頂点vに接続する少なくともn個の辺の集合である場合、K2n +1 −Fは区間彩色を持つ。
  • Fがn≥2の完全グラフK 2n+1の最大マッチングである場合、 K 2n+1 −Fには区間彩色はありません。
  • n ≤ t ≤ n ( n + 1 ) 2 {\displaystyle {\frac {n(n+1)}{2}}} の場合、n次元立方体Qnには区間t色付けがあります。

二部グラフの区間辺彩色

  • 任意のm, n ∈ Nに対して、完全二部グラフK m,nは区間彩色可能であり、

(1) w ( K m,n ) = m + n − gcd(m, n)、

(2) W ( K m,n ) = m + n − 1,

(3) w ( K m,n ) ≤ t ≤ W ( K m,n ) ならば、K m,nは区間t彩色を持つ。

  • Gが二部グラフの場合、χ′(G) = ∆(G)となる。
  • G ∈ Nならば、任意のm, n ∈ Nに対してG[ K m,n ] ∈ Nが成り立つ。さらに任意のm, n ∈ Nに対して、

w(G[ Km ,n ])≤(w(G)+1)(m+n)−1かつW(G[ Km ,n ])≥(W(G)+1)(m+n)−1。

  • Gが連結な二部グラフでG∈Nならば、W(G)≤diam(G)(∆(G)−1)+1となる。

平面グラフの区間エッジ彩色[4]

外平面グラフの区間辺彩色はGiaroとKubaleによって研究され、すべての外平面二部グラフは区間彩色可能であることが証明された。[5]

  • G = G 1 eG 2（ただし、G 1とG 2は区間彩色を持ち、eは外部ラベルを持つ）とすると、Gは区間彩色を持つ。

証明: c 1 を'G 1 'の区間彩色とし、e =xy がxとyに接続する辺の中で最小のラベルを取得するものとし、 c 1 (e)=0 とする。G 1の区間彩色c 1において、eがxとyに接続する辺の中で最大のラベルを取得するものとし、c 2 (e)=i とする。そして、 Gの区間彩色c を、 (e ') ∈E(G 1 )の 場合c (e' ) = c 1 (e') 、 (e') ∈ E(G 1 )の場合 c (e') = c 2 (e') - i として構築する。

  • G が三角形を分離せずに少なくとも 4 次を持つ外平面グラフである場合、それは区間彩色を持ちます。
  • G をグラフHのある区間彩色の下でいくつかの分割辺を削除することによって得られるグラフとする。このとき、Gは区間彩色可能である。
  • Hを、独立した三角形を持たない外平面三角形分割とし、H = H 1、----- H mを、接続辺をe 1、----、e m-1とする分解とします。Hから接続辺を削除してGを取得した場合、G には区間彩色が適用されます。
  • n頂点を持つ任意の平面区間彩色可能グラフGに対してt(G) ≤(11/6) nが成り立つ。

小さな頂点次数を持つ二正則二部グラフの区間辺彩色

二部グラフが(a, b)-双正則グラフであるとは、一方のグラフのすべての頂点が次数aを持ち、もう一方のグラフのすべての頂点が次数bを持つことを意味する。このようなグラフはすべて区間彩色可能であると予想されている。ハンセンは、∆(G) ≤ 3を満たすすべての二部グラフGが区間彩色可能であることを証明した。

公平なK間隔エッジカラーリング

グラフのk区間辺彩色は、その辺集合EがK個の部分集合E 1 ,E 2 ,...,E kに分割され、 E i が独立集合であり、かつ条件 -1 ≤ E i ≤ E j ≤ 1 がすべての1 ≤ i ≤ k, 1 ≤ j ≤ kに対して成立する場合、公平なk区間辺彩色と呼ばれます。Gが公平な区間辺彩色となる最小の整数kは、Gの区間辺彩色の公平な彩色数と呼ばれ、 と表記されます。 χ e i e ( G ) {\displaystyle \chi _{eie}(G)}

アプリケーション

区間エッジカラーリングは、科学やスケジュール管理のさまざまな分野で幅広く応用されています。

  • 区間エッジカラーリングの基本的な応用例の一つは、重複のない授業の時間割を組むことです。この応用では、授業時間が頂点となり、同じ時間間隔を持つ授業はエッジを共有します。エッジを着色するために必要な色の数は、重複なく授業を実施するために必要な授業数です。これは、重複を避けながら2つ以上のイベントを計画する必要があるすべての場合に使用されます。
  • 同様のアプリケーションは、プロセッサの実行時間のスケジュール設定にも見られます。たとえば、分散ネットワークでのファイル転送のスケジュール設定、マルチコンピュータ システムでの診断テストのスケジュール設定、オープン ショップ システムでのタスクのスケジュール設定などです。この目的のためにさまざまなアルゴリズムが開発されています。
  • 完全グラフの区間エッジ彩色可能性は、各チームが互いに対戦するようなトーナメントでの 2n 回のプレイのスケジュール設定に役立ちます。
  • 平面グラフと二部グラフの区間エッジ彩色可能性の研究により、他の多くの応用が生まれています。

推測

  • 任意のm,n∈Nに対して、gcd(m+1, n+1) = 1のときのみ、K1,m,n∈Nとなります。
  • Gがn頂点の平面グラフである場合、 Gの区間彩色で使用される色の最大数は最大で (3/2) nです。
  • 分離三角形のない外平面三角形分割から内部の辺を削除して得られる外平面グラフは、区間彩色可能です。

参考文献

  1. ^ abc アスラティアン、AS; Kamilyan, RR (1987)、「マルチグラフのエッジの間隔カラーリング」、Tonoyan, RN (編)、Прикладная математика。 Вып。 5. [応用数学。 No.5 ]（ロシア語）、エレバン：エレバン。大学、  25–34、130–131、MR 1003403 ​
  2. ^ abc Petrosyan, PA (2010)、「完全グラフと n次元立方体の区間辺彩色」、離散数学、310 ( 10–11 ): 1580–1587、doi :10.1016/j.disc.2010.02.001、MR  2601268
  3. ^ Asratian, AS; Kamalian, RR (1994)、「グラフの区間辺彩色の調査」、Journal of Combinatorial Theory、シリーズB、62 (1): 34– 43、doi : 10.1006/jctb.1994.1053、MR  1290629
  4. ^ ab Axenovich, Maria A. (2002), 「平面グラフの区間彩色について」, Proceedings of the Thirty-Third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002) , Congressus Numerantium, vol. 159, pp.  77– 94, MR  1985168
  5. ^ Giaro, Krzysztof; Kubale, Marek (2004)、「多段システムにおけるゼロ・ワンタイム演算のコンパクトスケジューリング」、離散応用数学、145 (1): 95– 103、doi :10.1016/j.dam.2003.09.010、MR  2108435

参照

Retrieved from "https://en.wikipedia.org/w/index.php?title=Interval_edge_coloring&oldid=1313317661"