完全に順序付け可能なグラフ

グラフ理論において、完全に順序付け可能なグラフとは、そのグラフの頂点を、その順序付けによる貪欲彩色アルゴリズムが、与えられたグラフのすべての誘導サブグラフを最適に彩色するような方法で順序付けることができるグラフである。完全に順序付け可能なグラフは、完全グラフの特殊なケースを形成し、弦グラフ、比較可能性グラフ、距離遺伝グラフなどを含む。ただし、グラフが完全に順序付け可能かどうかをテストすることは、NP完全である。

貪欲彩色アルゴリズムは、グラフGの頂点の与えられた順序に適用された場合、グラフの頂点を順に検討し、各頂点に最初の使用可能な色、つまり隣接する頂点で使用される色のセットの最小除外値を割り当てます。頂点の順序が異なると、このアルゴリズムが使用する色の数も異なる場合があります。最適な彩色につながる順序は常に存在しますが (たとえば、頂点を色で並べ替えることによって最適な彩色から決定される順序がこれに該当します)、それを見つけるのは難しい場合があります。完全に順序付け可能なグラフは、グラフ自体だけでなく、その誘導されたサブグラフすべてに対して貪欲アルゴリズムに最適な順序があるグラフとして定義されます。

より正式には、グラフGが完全に順序付け可能であるとは、 Gの頂点の順序 π が存在し、Gのすべての誘導サブグラフが、サブグラフの頂点によって誘導される π の部分列を使用した貪欲アルゴリズムによって最適に色付けされる場合を言う。順序 π がこの特性を持つのは、abcd が誘導パスである 4 つの頂点a、b、c、dが存在せず、順序付けにおいてa がb の前に現れ、順序付けにおいてc がd の後に現れる場合である。 ^[1]

完全に順序付け可能なグラフはNP完全である。^[2]しかし、特定の順序付けがグラフの完全な順序付けであるかどうかをテストするのは簡単です。したがって、グラフが完全に順序付け可能であることが既にわかっている場合でも、グラフの完全な順序付けを見つけることはNP困難です。

完全に順序付け可能なグラフはすべて完全グラフである。^[1]

弦グラフは完全に順序付け可能であり、弦グラフの完全な順序付けは、グラフの完全な消去順序付けを逆にすることで見つけることができる。したがって、完全な順序付けに貪欲な色付けを適用すると、弦グラフを最適に色付けするための効率的なアルゴリズムが提供される。比較可能性グラフも完全に順序付け可能であり、完全な順序付けはグラフの推移的方向の位相的順序付けによって与えられる。^[1]許容グラフの補グラフは完全に順序付け可能である。^[3]

完全に順序付け可能なグラフの別のクラスは、グラフGによって与えられ、Gの 5 つの頂点のすべての部分集合において、5 つの頂点のうち少なくとも 1 つが、5 つの頂点のうちの別の頂点の閉近傍の部分集合 (または等しい) である閉近傍を持つ。同様に、これらは、集合包含によって順序付けられた閉近傍の部分順序が最大で 4 の幅を持つグラフである。5 頂点サイクル グラフの近傍部分順序は幅 5 であるため、4 は完全な順序付け可能性を保証する最大幅である。弦グラフと同様に (より一般的には完全に順序付け可能なグラフとは異なり)、幅 4 のグラフは多項式時間で認識可能である。^[4]

弦グラフの完全消去順序と完全順序の中間の概念は、半完全消去順序である。消去順序では、中央の頂点が3つのうち最初に消去される3頂点誘導パスは存在せず、半完全消去順序では、中央の2つの頂点のうちの1つが最初に消去される4頂点誘導パスは存在しない。したがって、この順序の逆は完全順序の要件を満たすため、半完全消去順序を持つグラフは完全に順序付け可能である。^[5]特に、弦グラフの完全消去順序を見つけるために使用される同じ辞書式幅優先探索アルゴリズムは、距離遺伝グラフの半完全消去順序を見つけるために使用でき、したがってこれも完全に順序付け可能である。^[6]

すべての頂点順序が完全順序であるグラフはコグラフです。コグラフは 4 つの頂点によって誘導されるパスを持たないグラフであるため、完全順序のパス順序要件に違反することはできません。

完全に順序付け可能なグラフには、他にもいくつかのクラスが知られている。^[7]

• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999)、「グラフクラス: 概観」、SIAM Monographs on Discrete Mathematics and Applications、ISBN 0-89871-432-X
• Christen, Claude A.; Selkow, Stanley M. (1979)、「グラフの完全な着色特性」、Journal of Combinatorial Theory、シリーズ B、27 (1): 49–59、doi :10.1016/0095-8956(79)90067-4、MR  0539075
• Chvátal, Václav (1984)、「完全に順序付け可能なグラフ」、Berge, Claude ; Chvátal, Václav (編)、Topics in Perfect Graphs、Annals of Discrete Mathematics、vol. 21、アムステルダム: North-Holland、pp. 63–68Maffray (2003) より引用。
• Chvátal, Václav ; Hoàng, Chính T.; Mahadev, NVR; De Werra, D. (1987)、「完全に順序付け可能なグラフの 4 つのクラス」、Journal of Graph Theory、11 (4): 481–495、doi :10.1002/jgt.3190110405。
• ドラガン、FF; Nicolai, F. (1995)、距離遺伝グラフの LexBFS 順序付け、Schriftenreihe des Fachbereichs Mathematik der Univ.デュイスブルク SM-DU-303Brandstädt、Le、Spinrad（1999）による引用。
• フェルスナー、ステファン; ラガヴァン、ヴィジェイ; スピンラッド、ジェレミー (2003)、「小さな幅の順序と小さなディルワース数のグラフの認識アルゴリズム」、Order、20 (4): 351–364 (2004)、doi :10.1023/B:ORDE.0000034609.99940.fb、MR  2079151、S2CID  1363140。
• ゴルンビック、マーティン・チャールズ; モンマ、クライド・L.;トロッター、ウィリアム・T.・ジュニア(1984)、「許容グラフ」、離散応用数学、9 (2): 157–170、doi : 10.1016/0166-218X(84)90016-7、MR  0761599
• Hoàng, Chính T.; Maffray, Frédéric; Olariu, Stephan; Preissmann, Myriam (1992)、「完全に順序付け可能なグラフの魅力的なクラス」、離散数学、102 (1): 67–74、doi : 10.1016/0012-365X(92)90348-J。
• Hoàng, Chính T.; Reed, Bruce A. (1989)、「完全に順序付け可能なグラフのいくつかのクラス」、Journal of Graph Theory、13 (4): 445–463、doi :10.1002/jgt.3190130407。
• Maffray, Frédéric (2003)、「完全グラフの色付けについて」、Reed, Bruce A. ; Sales, Cláudia L. (編)、Recent Advances in Algorithms and Combinatorics、CMS Books in Mathematics、vol. 11、Springer-Verlag、pp. 65–84、doi :10.1007/0-387-22444-0_3、ISBN 0-387-95434-1。
• Middendorf, Matthias; Pfeiffer, Frank (1990)、「完全に順序付け可能なグラフを認識する複雑さについて」、離散数学、80 (3): 327–333、doi : 10.1016/0012-365X(90)90251-C。
• パヤン、チャールズ（1983）、「完全性とディルワース数」、離散数学、44（2）：229–230、doi：10.1016/0012-365X（83）90064-X、MR  0689816。