紛争のないカラーリング

競合のない彩色は、グラフ彩色の概念をハイパーグラフに一般化したものである。^[1]

意味

ハイパーグラフ Hには、頂点集合Vと辺集合Eがあります。各辺は頂点のサブセットです (グラフでは、各辺には最大 2 つの頂点が含まれますが、ハイパーグラフでは 3 つを超える頂点が含まれる場合があります)。

色付けとは、Vの各頂点に色を割り当てることです。

各辺の少なくとも 1 つの頂点が一意の色を持つ場合、色付けは競合しません。H がグラフの場合、この条件はグラフの正当な色付けの標準条件になります。つまり、すべての辺に隣接する 2 つの頂点は異なる色を持つ必要があります。

アプリケーション

競合のないカラーリングは、携帯電話のアンテナに周波数帯域を割り当てる場合、センサーネットワークのバッテリー消費の側面、RFIDプロトコルなどの文脈で発生します。^[1]

特別なケース

よくある特殊なケースとして、頂点が平面上の点であり、辺が同じ円板に含まれる点の部分集合である場合があげられる。この設定では、点の色付けは、その集合の点を少なくとも 1 つ含むすべての閉円板Dに対して、ちょうど 1 回出現する色がある場合、競合がないという。平面上のn点のすべての集合の競合のない色付けでは、絶対定数c > 0 に対して、少なくともc log n色を使用する。同じことは円板だけでなく、任意の凸体の相似コピーにも当てはまる。^[2]

もう 1 つの特殊なケースは、頂点がグラフの頂点であり、辺が隣接頂点の集合である場合です。この設定では、すべての頂点vについて、 vとその隣接頂点のうち 1 つの頂点にのみ割り当てられた色がある場合、頂点の色付けは競合がないと呼ばれます。この設定では、ハドヴィガー予想の競合のない変種が成り立ちます。グラフG にマイナーとしてK _k₊₁が含まれていない場合、最大k色の競合のない色付けがあります。平面グラフの場合、競合のない色付けには 3 色が必要な場合があり、常に 3 色で十分です。平面グラフが1色の競合のない色付けを持つかどうか、および平面グラフが2色の競合のない色付けを持つかどうかを判断することは NP 完全です。^[3]

外部リンク

YouTubeの「Conflict-Free Coloring (Shakhar Smorodinsky)」

参考文献

^ ab スモロディンスキー、シャハル (2013)、バーラーニ、イムレ;ボレツキー、カーロリ J.トート、ガボール・フェヘス。 Pach、János (編)、「Conflict-Free Coloring and its Applications」、Geometry — Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth、Bolyai Society Mathematical Studies、vol. 24、ベルリン、ハイデルベルク: Springer、pp. 331–389、arXiv : 1005.3616、doi :10.1007/978-3-642-41498-5_12、ISBN 978-3-642-41498-5, S2CID 174683 , 2021-01-20取得
^ パッハ、ヤーノス;トート、ゲザ (2003)、アロノフ、ボリス。バス、サガタ。パッハ、ヤーノス。 Sharir、Micha (編)、「Conflict-free Colorings」、Discrete and Computational Geometry: The Goodman-Pollack Festschrift、Algorithms and Combinatorics、vol. 25、ベルリン、ハイデルベルク: Springer、pp. 665–671、doi :10.1007/978-3-642-55566-4_30、ISBN 978-3-642-55566-4、2021-01-20取得
^ Abel, Zachary; Alvarez, Victor; Demaine, Erik D.; Fekete, Sándor P.; Gour, Aman; Hesterberg, Adam; Keldenich, Phillip; Scheffer, Christian (2018-01-01). 「グラフの衝突のない着色」. SIAM Journal on Discrete Mathematics . 32 (4): 2675–2702. doi :10.1137/17M1146579. hdl : 1721.1/122951 . ISSN 0895-4801.

[:0-1] スモロディンスキー、シャハル (2013)、バーラーニ、イムレ;ボレツキー、カーロリ J.トート、ガボール・フェヘス。 Pach、János (編)、「Conflict-Free Coloring and its Applications」、Geometry — Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth、Bolyai Society Mathematical Studies、vol. 24、ベルリン、ハイデルベルク: Springer、pp. 331–389、arXiv : 1005.3616、doi :10.1007/978-3-642-41498-5_12、ISBN 978-3-642-41498-5, S2CID 174683 , 2021-01-20取得

[2] パッハ、ヤーノス;トート、ゲザ (2003)、アロノフ、ボリス。バス、サガタ。パッハ、ヤーノス。 Sharir、Micha (編)、「Conflict-free Colorings」、Discrete and Computational Geometry: The Goodman-Pollack Festschrift、Algorithms and Combinatorics、vol. 25、ベルリン、ハイデルベルク: Springer、pp. 665–671、doi :10.1007/978-3-642-55566-4_30、ISBN 978-3-642-55566-4、2021-01-20取得

[3] Abel, Zachary; Alvarez, Victor; Demaine, Erik D.; Fekete, Sándor P.; Gour, Aman; Hesterberg, Adam; Keldenich, Phillip; Scheffer, Christian (2018-01-01). 「グラフの衝突のない着色」. SIAM Journal on Discrete Mathematics . 32 (4): 2675–2702. doi :10.1137/17M1146579. hdl : 1721.1/122951 . ISSN 0895-4801.