着色完了

グラフ理論において、完全彩色とは、すべての色のペアが少なくとも1 組の隣接する頂点に現れる(適切な)頂点彩色です。同様に、完全彩色は、色クラスのペアをマージすることによって、より少ない色の適切な彩色に変換できないという意味で最小です。グラフ $Gの$ 無彩色数 $ψ($ $G$ $)は、$ $G$ の任意の完全彩色で可能な色の最大数です。

完全着色は調和着色の逆であり、調和着色では、すべての色のペアが最大で1 組の隣接する頂点に現れる必要があります。

複雑性理論

$ψ(G)$ を見つけることは最適化問題です。完全着色の決定問題は次のように表現できます。

例: グラフ

G = (V, E)

と正の整数

k

質問: V

を

k

個以上の互いに素な集合

V

1

、

V

2

、\dots、

V

k

に分割して、各

V

i が

G

に対して独立集合となり、異なる集合の各ペア

V

i

、

V

j

、

V

i

\cup

V

j

が独立集合とならないようにすることは可能ですか。

無彩色数を決定することはNP困難である。無彩色数が与えられた数より大きいかどうかを決定することはNP完全であり、これは1978年にYannakakisとGavrilによって最小最大マッチング問題からの変換によって示された。^[1]

グラフを最小の数の色で着色することは完全な着色でなければならないことに注意してください。したがって、完全な着色で色の数を最小化することは、標準的なグラフ着色問題を言い換えただけです。

アルゴリズム

任意のkに対して、与えられたグラフの無彩色数が少なくともkであるかどうかを線形時間で判定することが可能である。^[2]

最適化問題は近似を許容し、近似率内で近似可能である。^[3] $O\left(|V|/{\sqrt {\log |V|}}\right)$

グラフの特別なクラス

無彩色数問題のNP完全性は、二部グラフ^[2]、二部グラフの補グラフ（つまり、2つ以上の頂点の独立した集合を持たないグラフ）^[1]、コグラフと区間グラフ^[4]、さらには木^[5]などの特別なグラフのクラスにも当てはまります。

木の補集合の場合、無彩色数は多項式時間で計算できる。^[6]木の場合、無彩色数は定数倍で近似できる。^[3]

n次元超立方体グラフの無彩色数はに比例することが知られているが、比例定数は正確にはわかっていない。^[7] ${\sqrt {n2^{n}}}$

参考文献

^ ab Michael R. GareyおよびDavid S. Johnson (1979)、「コンピュータとイントラクタビリティ: NP完全性理論へのガイド」、WH Freeman、ISBN 978-0-7167-1045-5A1.1: GT5、191ページ。
^ ab Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986)、「グラフの無彩色数について」、Journal of Combinatorial Theory、シリーズ B、40 (1): 21–39、doi : 10.1016/0095-8956(86)90062-6。
^ ab Chaudhary, Amitabh; Vishwanathan, Sundar (2001)、「無彩色の数の近似アルゴリズム」、Journal of Algorithms、41 (2): 404–416、CiteSeerX 10.1.1.1.5562、doi :10.1006/jagm.2001.1192、S2CID 9817850 。
^ Bodlaender, H. (1989)、「無彩色数はコグラフと区間グラフに対してNP完全である」、Inf. Process. Lett.、31 (3): 135–138、doi :10.1016/0020-0190(89)90221-4、hdl : 1874/16576。
^ Manlove, D.; McDiarmid, C. (1995)、「木の調和的着色の複雑さ」、離散応用数学、57 (2–3): 133–144、doi : 10.1016/0166-218X(94)00100-R。
^ Yannakakis, M.; Gavril, F. (1980)、「グラフのエッジ支配集合」、SIAM Journal on Applied Mathematics、38 (3): 364–372、doi :10.1137/0138030。
^ Roichman, Y. (2000)、「超立方体の無彩色数について」、組合せ理論ジャーナル、シリーズ B、79 (2): 177–182、doi : 10.1006/jctb.2000.1955。

外部リンク

NP最適化問題の概要
キース・エドワーズ著『調和のとれた色彩と無彩色の数の書誌』

[gj-1] Michael R. GareyおよびDavid S. Johnson (1979)、「コンピュータとイントラクタビリティ: NP完全性理論へのガイド」、WH Freeman、ISBN 978-0-7167-1045-5A1.1: GT5、191ページ。

[fhhm-2] Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986)、「グラフの無彩色数について」、Journal of Combinatorial Theory、シリーズ B、40 (1): 21–39、doi : 10.1016/0095-8956(86)90062-6。

[cv-3] Chaudhary, Amitabh; Vishwanathan, Sundar (2001)、「無彩色の数の近似アルゴリズム」、Journal of Algorithms、41 (2): 404–416、CiteSeerX 10.1.1.1.5562、doi :10.1006/jagm.2001.1192、S2CID 9817850 。

[4] Bodlaender, H. (1989)、「無彩色数はコグラフと区間グラフに対してNP完全である」、Inf. Process. Lett.、31 (3): 135–138、doi :10.1016/0020-0190(89)90221-4、hdl : 1874/16576。

[5] Manlove, D.; McDiarmid, C. (1995)、「木の調和的着色の複雑さ」、離散応用数学、57 (2–3): 133–144、doi : 10.1016/0166-218X(94)00100-R。

[6] Yannakakis, M.; Gavril, F. (1980)、「グラフのエッジ支配集合」、SIAM Journal on Applied Mathematics、38 (3): 364–372、doi :10.1137/0138030。

[7] Roichman, Y. (2000)、「超立方体の無彩色数について」、組合せ理論ジャーナル、シリーズ B、79 (2): 177–182、doi : 10.1006/jctb.2000.1955。