グラフ理論において、部分色付けとは、グラフの頂点に色を割り当てることであり、各色クラスが頂点同士が素なクリークの和集合を誘導する。つまり、各色クラスはクラスターグラフを形成する。
グラフGのサブ彩色数χ S ( G )は、 Gの任意のサブ彩色に必要な最小の色数です。
サブカラーリングとサブクロマティック数は、Albertson ら (1989) によって導入されました。
グラフの すべての適切な彩色と共彩色は部分彩色でもあるため、任意のグラフのサブ彩色数は最大で共彩色数に等しく、共彩色数は最大で彩色数に等しくなります。
部分彩色は、彩色と同様にNP完全であるという意味で、正確に解くのと同じくらい難しい。より具体的には、平面グラフのサブ彩色数が2以下であるかどうかを判定する問題は、たとえそれが
- 最大次数4の三角形のないグラフ（Gimbel & Hartman 2003）（Fiala et al. 2003）
- 最大次数4の比較グラフ（Ochem 2017）
- 最大次数4の二部グラフの折れ線グラフ（Gonçalves & Ochem 2009）
- 胴回り5のグラフ（Montassier & Ochem 2015）。
コグラフのサブクロマティック数は多項式時間で計算できる (Fiala et al. 2003)。任意の固定整数 r に対して、区間グラフ と順列グラフのサブクロマティック数が最大で r であるかどうかを多項式時間で判定できる(Broersma et al. 2002)。
参考文献
- アルバートソン, MO; ジェイミソン, RE; ヘデトニエミ, ST; ロック, SC (1989)「グラフのサブクロマティック数」,離散数学, 74 ( 1– 2): 33– 49, doi : 10.1016/0012-365X(89)90196-9。
- Broersma, Hajo; Fomin, Fedor V.; Nesetril, Jaroslav; Woeginger, Gerhard (2002)「サブカラーリングについてさらに詳しく」（PDF） , Computing , 69 (3): 187– 203, doi :10.1007/s00607-002-1461-1, S2CID 24777938。
- Fiala, J.; Klaus, J.; Le, VB; Seidel, E. (2003)、「グラフサブカラーリング：複雑性とアルゴリズム」、SIAM Journal on Discrete Mathematics、16 (4): 635– 650、CiteSeerX 10.1.1.3.183、doi :10.1137/S0895480101395245。
- ギンベル、ジョン；ハートマン、クリス（2003）「サブカラーリングとグラフのサブクロマティック数」、離散数学、272（2-3）：139-154、doi：10.1016/S0012-365X（03）00177-8。
- ゴンサルヴェス、ダニエル; オケム、パスカル (2009)、「星と芋虫の樹冠性について」、離散数学、309 (11): 3694– 3702、doi : 10.1016/j.disc.2008.01.041。
- Montassier, Mickael; Ochem, Pascal (2015)、「近似色付け：非色付けグラフとNP完全性」、Electronic Journal of Combinatorics、22 (1): #P1.57、arXiv : 1306.0752、doi :10.37236/3509、S2CID 59507。
- Ochem, Pascal (2017)、「2-subcoloringは平面比較グラフに対してNP完全である」、Information Processing Letters、128 : 46–48、arXiv : 1702.01283、doi :10.1016/j.ipl.2017.08.004、S2CID 22108461。
