グラフ理論において、グラフGの共彩色とは、各色クラスがG内またはGの補集合において独立な集合を形成するように頂点に色を割り当てることである。Gの共彩色数z( G )は、Gのあらゆる共彩色に必要な最小の色数である。共彩色数が 2 であるグラフは、まさに二部グラフ、二部グラフの補グラフ、および分割グラフである。
各色クラスがクリークまたは独立であるという要件は、色分けの要件(各色クラスは独立した集合でなければならない) よりも弱く、部分色分けの要件(各色クラスはクリークの互いに素な和集合でなければならない) よりも強いため、Gの共色数はGの彩色数以下であり、 Gの亜彩色数以上であることが分かります。
共彩色は、Lesniak & Straight (1977) によって命名され、初めて研究されました。Jørgensen (1995) は臨界3共彩色グラフを特徴づけ、Fomin, Kratsch & Novelli (2002) はグラフの共彩色数を近似するアルゴリズムを記述しました。Zverovich (2000) は、グラフ彩色による完全グラフの定義に類似した完全共彩色グラフのクラスを定義し、これらのグラフの禁制部分グラフによる特徴づけを行いました。
参考文献
- Fomin, Fedor V.; Kratsch, Dieter; Novelli, Jean-Christophe (2002)「最小共色近似」, Inf. Process. Lett. , 84 (5): 285– 290, doi :10.1016/S0020-0190(02)00288-0, S2CID 17733740。
- ギンベル、ジョン; ストレート、H. ジョセフ (1987)、「コクロマティック理論におけるいくつかのトピック」、グラフと組合せ論、3 (1): 255– 265、doi :10.1007/BF01788548、S2CID 8218390。
- Jørgensen, Leif K. (1995)、「臨界3-コクロマティックグラフ」、Graphs and Combinatorics、11 (3): 263– 266、doi :10.1007/BF01793013、S2CID 38851896。
- Lesniak, L.; Straight, HJ (1977)、「グラフの共色数」、Ars Combinatoria、3 : 39– 46。
- ストレート、HJ（1979）、「コクロマティック数とグラフの種数」、グラフ理論ジャーナル、3（1）：43-51、doi：10.1002/jgt.3190030106。
- Zverovich, Igor V. (2000), Perfect cochromatic graphs, Research report RRR 16-2000, Rutgers University Center for Operations Research, archived from the original on 2016-03-03 , retrieved 2006-10-16。
