発生率の色分け

グラフ理論では、色付けという行為は一般に、グラフ内の頂点、辺、または面にラベルを割り当てることを意味します。発生色付けは、辺と頂点の各発生に一定の制約の下で色が割り当てられる 特殊なグラフ ラベル付けです。

以下のGは、空でない頂点集合（空でない）V ( G )、辺集合E ( G )、最大次数Δ( G )を持つ単純なグラフを表します。

定義。接続は、 の端点である ( v、e ) のペアとして定義されます。簡単に言えば、頂点v は辺eに接続していると言えます。2 つの接続 ( v、e ) と ( u、f ) は、次のいずれかが当てはまる場合、 隣接または近隣していると言われます。${\displaystyle v\in V(G)}$${\displaystyle e\in E(G).}$

• v = u、e ≠ f
• e = f、v ≠ u
• e = { v , u }、f = { u , w } かつv ≠ w です。

定義。I ( G ) をGのすべての発生の集合とします。 Gの発生彩色は、隣接する発生で異なる値を取る関数 です(簡略化された表記c ( v , u ) をc (( v , e ) )の代わりに使用します)。グラフGの発生彩色に必要な最小の色の数は、Gの発生彩色数または発生彩色数と呼ばれ、次のように表されます。この表記法は、1993 年に Jennifer J. Quinn MasseyとRichard A. Brualdiによって導入されました。${\displaystyle c:I(G)\to \mathbb {N} }$${\displaystyle \chi_{i}(G).}$

入射彩色の概念は、1993 年に Brualdi と Massey によって導入され、Δ( G )で境界が定められました。最初に、木、完全二部グラフ、完全グラフの入射彩色数が発見されました。彼らはまた、すべてのグラフが Δ( G ) + 2 色を使用した入射彩色を持つことができると予想しました (入射彩色予想 - ICC)。この予想は Guiduli によって反証され、彼は入射彩色の概念が Alon と Algor によって導入された有向星樹木性ケースであることを示しました^[1]。彼の反例では、入射彩色数は最大でも Δ( G ) + O(log Δ( G )) であることを示しました。^[2]

Chen らは、パス、ファン、サイクル、ホイール、完全三部グラフ、およびエッジホイールの追加の発生彩色数を発見しました。数年後、Shiu らは、この予想が、3 次ハミルトン グラフなどの特定の3 次グラフに当てはまることを示しました。彼は、最大次数 4 の外平面グラフの場合、発生彩色数は 5 ではないことを示しました。現在、さまざまなグラフ クラスの発生彩色数の境界が判明しています。

命題。 ${\displaystyle \chi _{i}(G)\geq \Delta (G)+1.}$

証明。v をGの最大次数 Δ の頂点とします。を頂点vに接続する辺とします。 考慮するΔ + 1 接続のすべてのペア、つまり は隣接していることがわかります。 したがって、これらの接続は異なる色を使用して色付けする必要があります。 ${\displaystyle e_{1},e_{2},\ldots ,e_{\Delta }}$${\displaystyle e_{1}=\{v,w\}.}$${\displaystyle (v,e_{1}),(v,e_{2}),\ldots ,(v,e_{\Delta }),(w,e_{1})}$

この境界は木と完全グラフによって達成されます。

• Gが少なくとも2つの頂点を持つ完全グラフである場合、${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$
• Gが少なくとも2つの頂点を持つ木である場合、${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

主な結果はBrualdiとMassey (1993)によって証明された。Shiu、Sun、Wuはグラフが満たすべき特定の条件を提案した。${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• m ≥ n ≥ 2の完全二部グラフ の発生彩色数はm + 2 です。${\displaystyle K_{m,n}}$
• ${\displaystyle \chi _{i}(C_{n})\leq 4}$そして${\displaystyle \chi _{i}(C_{3n})=3.}$

正方形メッシュ、ハニカムメッシュ、六角形メッシュなどのメッシュの入射色付けを行うアルゴリズムがいくつか紹介されている^{[3] 。これらのアルゴリズムは最適である。各メッシュについて、入射色は最小の色数で線形時間内に作成できる。正方形メッシュ、ハニカムメッシュ、六角形メッシュの入射色付けには∆(} G )+1色が必要である ことがわかった。

• 正方形メッシュの入射色数は 5 です。
• 六角形メッシュの入射色数は 7 です。
• ハニカムメッシュの入射色数は4です。

Chen、Wang、Pangは、Gが∆( G )>4のHalinグラフである場合、 ∆( G )=3または4のHalinグラフの場合、Jing-Zhe Quはそれぞれ5または6になることを示しました。低次数のHalinグラフの発生色数がΔ( G )+1であるかどうかは、まだ未解決の問題です。 ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$${\displaystyle \chi_{i}(G)}$

ShiuとSunは、以外のすべての3次HalinグラフにはΔ( G )+2色 の発生色があることを証明した。Su、Meng、Guoはこの結果をすべての擬似Halinグラフに拡張した。${\displaystyle K_{4}}$

ハリングラフGに木 Tが含まれる場合、^[4]${\displaystyle \chi _{i}(G^{2})\leq \Delta (T^{2})+\Delta (T)+8.}$

DL Chen、PCB Lam、WC Shiu は、立方グラフGの発生彩色数は最大で ∆( G ) + 2 であると予想しました。彼らは、ハミルトン立方グラフなどの特定の立方グラフについてこれを証明しました。これらの結果に基づいて、MH Dolama、E. Sopena、X. Zhu (2004) は、 が∆( G ) + c （cは固定定数）で制限されるグラフクラスを研究しました。^[5] GのすべてのサブグラフHについて、 Hの最小次数が最大で k である場合、グラフはk生成であると言われます。 ${\displaystyle \chi_{i}(G)}$

• k退化したグラフGの発生彩色数は最大で∆( G )+ 2k −1である。
• K4マイナーフリーグラフGの発生彩色数は最大∆(G)+2であり_、厳しい境界を形成します。
• 平面グラフGの発生彩色数は最大∆( G )+7である。

切断頂点vを持つ外平面グラフ Gを考えます。G – vは、およびの和集合です。(それぞれ) を頂点v上の誘導サブグラフ、 (それぞれ)の頂点とします。このとき、はの最大値であり、はGにおける頂点vの次数です。 ${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle \chi_{i}(G)}$${\displaystyle \chi _{i}(G_{1}),\chi _{i}(G_{2})}$${\displaystyle 1+d_{G}(v)}$${\displaystyle d_{G}(v)}$

外平面グラフGの発生彩色数は最大で ∆( G ) + 2 です。 ∆( G ) > 3の外平面グラフの場合、発生彩色数は ∆( G ) + 1 です。

外平面グラフはK4_マイナーフリーグラフなので、(Δ+2,2)入射彩色を受け入れる。^{[5] [6]} Δ( G )=3および2連結外平面グラフを持つ外平面グラフGの入射彩色数の解は未解決の問題である。

弦リングはリング ネットワークのバリエーションです。通信における弦リングの使用は、リング トポロジーやその他の解析構造 (メッシュ、ハイパーキューブ、ケイリーのグラフなど) を持つ相互接続ネットワークよりも優れているため、非常に広範囲にわたります。Arden と Lee ^{[7] は}、3 次弦リング、つまり、各ノードがネットワーク内の他のノードへの弦と呼ばれる追加リンクを持つリング構造ネットワークを初めて提案しました。分散ループ ネットワークは、リング ネットワークのすべての頂点に 2 つの追加弦を追加することによって構築される 4 次弦リングです。

N個のノードと弦の長さd上の弦環は、 CR ( N , d )で表され、次のように定義されるグラフです。

${\displaystyle {\begin{aligned}V(G)&=\{v_{0},v_{1},\ldots ,v_{N-1}\}\\E(G)&=\{v_{ i}v_{j}:ij\equiv 1,d{\bmod {N}}\}\end{aligned}}}$

これらのグラフは、コミュニケーションへの応用のために研究されています。Kung-Fu Ding、Kung-Jui Pai、Ro-Yu Wuは、弦リングの発生色を研究しました。^[8]弦リングの発生彩度数を見つけるために、いくつかのアルゴリズムが策定されています。主な発見は次のとおりです。

${\displaystyle {\begin{aligned}\chi _{i}(CR(N,2))&={\begin{cases}5&5|N\\6&{\text{otherwise}}\end{cases}}\\\chi _{i}(CR(N,3))&={\begin{cases}5&5|N\\6&N\equiv 2{\bmod {5}}\end{cases}}\end{aligned}}}$

Keaitsuda Nakprasit と Kittikorn Nakprasit は、サイクルのべき乗の発生色付けを研究しました。2 k + 1 ≥ nの場合、n > 2 k + 1 と 仮定して次のように記述します。${\displaystyle C_{n}^{k}.}$${\displaystyle C_{n}^{k}=K_{n}}$

${\displaystyle n=(2k+1)t+r,\quad 1\leq t,\quad 0\leq r\leq 2k.}$

彼らの結果は次のように要約できる。^[9]

${\displaystyle {\begin{aligned}\chi _{i}(C_{n}^{k})&={\begin{cases}2k+1&r=0\\2k+2&1\leq r\leq t{\text{ または }}r=2k\end{cases}}&&k\geq 3\\\chi _{i}(C_{n}^{2})&={\begin{cases}5&5|n\\6&{\text{それ以外の場合}}\end{cases}}\end{aligned}}}$

入射色予想との関係は、次の観察によって示される。${\displaystyle \Delta (C_{n}^{k})=2k.}$

命題。^[10] Gをn次の単純連結グラフ、 mサイズ、支配数とする。すると${\displaystyle \gamma .}$${\displaystyle \chi _{i}(G)\geq {\tfrac {2m}{n-\gamma }}.}$

証明。グラフGの各辺を反対方向の 2 つの弧に分割して、グラフGから有向グラフ D ( G )を形成します。D ( G )の弧の総数は2 mであることがわかります。Guiduli ^[2]によると、Gの発生色は有向グラフ D ( G ) の適切な色付けに相当し、 2つの異なる弧とが隣接している場合、次の条件のいずれかが満たされます。(i) u = x ; (ii) v = xまたはy = u。弧の隣接の定義により、D ( G )の弧の独立集合はスターフォレストです。したがって、弧の最大独立集合は最大スターフォレストです。これは、少なくともカラークラスが必要であることを意味します。^[10]${\displaystyle {\overrightarrow {uv}}}$${\displaystyle {\overrightarrow {xy}}}$${\displaystyle {\tfrac {2m}{n-\gamma }}}$

この関係は、( r + 1)-入射彩色可能なr-正則グラフの特徴付けに広く使われてきた。r-正則グラフの入射彩色に関する主要な結果は、グラフGがr-正則グラフである場合、V ( G )がr + 1個の支配集合の互いに素な和集合である場合に限り、となることである。^[10]${\displaystyle \chi _{i}(G)=\chi _{i}(G^{2})=r+1}$

定義。有限部分集合は、その最小値と最大値の間のすべての数値が含まれる場合にのみ、 区間となります。${\displaystyle A\subset \mathbb {N} }$

定義。cをGの入射色とし、次のように定義する 。

${\displaystyle A_{c}(v)=\{c(v,e):(v,e)\in I(G)\}.}$

Gの区間接続彩色とは、Gの各頂点vに対して集合が区間となるような接続彩色c のことである。 ^{[11] [12]} Gの区間接続彩色数は、Gの区間接続彩色に使用される色の最小数である。これは次のように表される。区間接続彩色に色のみが使用される場合、それは最小であると言われること は明らかである。${\displaystyle A_{c}(v)}$${\displaystyle \chi _{ii}.}$${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).}$${\displaystyle \chi _{ii}}$

区間接続彩色の概念は、A. Malafiejska、R. Janczewski、M. Malafiejskiによって導入されました。彼らは二部グラフに対して証明しました。^{[13]正則二部グラフの場合、等式が成り立ちます。サブキュービック二部グラフは、4色、5色、または6色を使用した区間接続彩色が可能です。彼らはまた、∆(} G ) = 4 の二部グラフに対して、接続5色彩色可能性を線形時間で決定できることも証明しました。${\displaystyle \chi _{ii}(G)\leq \Delta (G)}$

発生彩色の分数バージョンは、2007年にヤンによって初めて導入されました。グラフGのr組発生k彩色は、グラフGの各発生にk色のセットからr色を割り当て、隣接する発生に互いに素な色のセットを与えることです。^{[14]定義により、1組発生}k彩色も発生k彩色であることは明らかです。

グラフGの分数入射彩色数は、G がr組の入射k彩色を許容するような分数の下限です。分数入射彩色は、コンピュータサイエンスのいくつかの分野で大きな応用があります。Guiduli による入射彩色結果に基づいて、^{[2] Yang は、任意のグラフの分数入射彩色数が最大で Δ(} G ) + 20 log Δ( G ) + 84であることを証明しました。彼はまた、分数入射彩色数が少なくとも Δ( G ) + Ω(log Δ( G )) であるグラフの存在も証明しました。 ${\displaystyle {\tfrac {k}{r}}}$

G をn頂点のグラフとし、はGの補集合を表すものとする。すると^{[10]これらの境界は}nのすべての値に対して厳密である。 ${\displaystyle G\neq K_{n},{\overline {K_{n}}}}$${\displaystyle {\overline {G}}}$${\displaystyle n+2\leq \chi _{i}(G)+\chi _{i}({\overline {G}})\leq 2n-1.}$

発生彩色ゲームはSDアンドレスによって初めて導入されました。^[15]これは頂点彩色ゲームの発生バージョンであり、グラフの頂点の代わりに発生が色付けされます。発生ゲーム彩色数は、発生彩色数のゲーム理論的類似物として定義された新しいパラメータです。

このゲームは、2 人のプレイヤー、アリスとボブが適切な発生色付けを構築するというものです。ルールは以下のとおりです。

• アリスとボブはグラフGの発生をk色のセットで色付けします。
• 彼らは交代で、色付けされていない出来事に適切な色付けを施しています。一般的には、アリスが始めます。
• 適切に色付けできない事象が発生した場合は、ボブが勝ちます。
• グラフのすべての発生箇所が適切に色付けされていれば、アリスが勝ちます。

グラフGの発生ゲーム彩色数は と表記され、発生彩色ゲームでアリスが勝つために必要な最小の色数です。これは、グラフの発生彩色数と無向グラフの場合のゲーム彩色数の考え方を統合したものです。Andres は、k退化したグラフの場合の の上限が 2Δ + 4 k − 2 であることを発見しました。この上限は、 Δ が少なくとも 5 kであるグラフの場合は2Δ + 3 k − 1 に改善されました。星、サイクル、十分に大きなホイールの発生ゲーム彩色数も決定されています。^[15] John Y. Kim (2011) は、大きなパスの発生ゲーム彩色数を正確に発見し、Andres が大きなホイールの発生ゲーム彩色数に関して述べた結果の正しい証明を与えました。^[16]${\displaystyle i_{g}(G)}$${\displaystyle i_{g}(G)}$

• L(h, k)-カラーリング
• 調和のとれたカラーリング
• 星の塗り絵
• トータルカラーリング
• 円形着色
• パスの色分け
• 着色不良
• ラジオカラーリング
• 非環式着色