分数着色

分数彩色は、分数グラフ理論として知られるグラフ理論の新しい分野のトピックです。これは、通常のグラフ彩色の一般化です。従来のグラフ彩色では、グラフの各頂点に何らかの色が割り当てられ、隣接する頂点 (エッジで接続された頂点) には異なる色を割り当てる必要があります。ただし、分数彩色では、グラフの各頂点に色のセットが割り当てられます。隣接する頂点に関する要件は依然として適用されるため、2 つの頂点がエッジで接続されている場合、それらの頂点に共通の色があってはなりません。

分数グラフの色付けは、従来のグラフの色付けの線形計画法緩和として考えることができます。実際、分数色付けの問題は、従来の色付けの問題よりも線形計画法のアプローチに非常に適しています。

グラフGのb倍彩色は、グラフの頂点にサイズbの集合を割り当て、隣接する頂点が互いに素な集合を受け取るようにすることです。 a : b彩色は、使用可能な色からのb倍彩色です。同様に、これはKneser グラフKG _{a , b}への準同型として定義できます。b倍彩色数は、 a : b彩色が存在する最小のaです。 ${\displaystyle \chi _{b}(G)}$

分数彩色数 は次のように定義されます。 ${\displaystyle \chi_{f}(G)}$

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

が劣加法的であるため、極限が存在することに注意してください。つまり、${\displaystyle \chi _{b}(G)}$${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G).}$

分数彩色数は、確率的な用語で同等に定義できます。は、分布から抽出された 独立集合Sが与えられた各頂点vに対して、 Gの独立集合上の確率分布が存在する最小のkです。${\displaystyle \chi_{f}(G)}$

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}.}$

我々は持っています：

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},}$

頂点推移グラフでは等式が成り立ち、ここでn ( G )はGの位数、α( G )は独立数である。^[1]

さらに：

${\displaystyle \omega (G)\leq \chi _{f}(G)\leq \chi (G),}$

ここでω( G )はクリーク数、は彩色数である。 ${\displaystyle \chi (G)}$

さらに、分数彩度数は対数係数内で彩度数を近似します。^[2]実際、

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).}$

クネザーグラフは、次のような例を示しています。 は任意に大きいです。なぜなら、${\displaystyle \chi (G)/\chi _{f}(G)}$${\displaystyle \chi (KG_{m,n})=m-2n+2,}$${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}.}$

グラフGの分数彩色数は、線形計画法の解として得ることができます。をGのすべての独立集合の集合とし、 を頂点x を含むすべての独立集合の集合とします。各独立集合Iに対して、非負の実変数x _Iを定義します。すると、の最小値は次のようになります。 ${\displaystyle \chi_{f}(G)}$${\displaystyle {\mathcal {I}}(G)}$${\displaystyle {\mathcal {I}}(G,x)}$${\displaystyle \chi_{f}(G)}$

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I},}$

以下を条件とする:

${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$

各頂点ごとに。 ${\displaystyle x}$

この線形計画法の双対は、整数概念クリーク数の有理数の緩和である「分数クリーク数」を計算する。つまり、任意の独立集合に割り当てられる合計重みが最大で1となるようなGの頂点の重み付けである。線形計画法の強い双対性定理は、両方の線形計画法の最適解が同じ値を持つことを保証する。ただし、各線形計画法はGの頂点の数に対して指数関数的なサイズになる可能性があり、グラフの分数彩色数を計算するのはNP 困難である点に注意すること。^[3]これは、多項式時間で解決できるグラフの辺を分数彩色する問題とは対照的である。これは、エドモンズのマッチング多面体定理の直接的な帰結である。^{[4] [5]}

分数グラフカラーリングの応用には、アクティビティのスケジューリングが含まれます。この場合、グラフGは競合グラフです。つまり、 G内のノードuとv間のエッジは、 uとv が同時にアクティブになることはできないことを意味します。言い換えると、同時にアクティブなノードの集合は、グラフG内の独立した集合である必要があります。

Gにおける最適な分数グラフ彩色は、各ノードが合計で (少なくとも) 1 時間単位アクティブであり、どの時点でもアクティブなノードのセットが独立セットであるような、可能な限り最短のスケジュールを提供します。上記の線形計画の解xがある場合は、すべての独立セットI を任意の順序で走査するだけです。各Iについて、 I内のノードを時間単位アクティブにします。一方、 Iにない各ノードは非アクティブです。 ${\displaystyle x_{I}}$

より具体的には、Gの各ノードは無線通信ネットワークにおける無線送信を表し、 Gのエッジは無線送信間の干渉を表します。各無線送信は合計で 1 時間単位アクティブである必要があります。最適な分数グラフ色付けにより、競合のない最小長スケジュール (または、同等に最大帯域幅スケジュール) が提供されます。

さらに、各ノードが 1 時間単位の間継続的にアクティブである必要がある(ときどきオンとオフを切り替えることなく) ことが要求される場合、従来のグラフ頂点カラーリングによって最適なスケジュールが提供されます。最初に色 1 のノードが 1 時間単位の間アクティブになり、次に色 2 のノードが 1 時間単位の間アクティブになります。繰り返しますが、どの時点でも、アクティブなノードのセットは独立したセットです。

一般に、分数グラフ彩色は非分数グラフ彩色よりも短いスケジュールを提供します。整数ギャップがあります。 デバイス（無線送信機など）のオン/オフを複数回切り替えるという代償を払って、より短いスケジュールを見つけることができる可能性があります。

• シャイナーマン、エドワード R. ; ウルマン、ダニエル H. (1997)、分数グラフ理論、ニューヨーク：ワイリー・インターサイエンス、ISBN 978-0-471-17864-4。
• ゴッズィル、クリス、ロイル、ゴードン（2001）、代数グラフ理論、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-95241-3。

• 分数マッチング