数学の分野であるグラフ理論において、グラフGのスター彩色とは、4つの頂点上のすべてのパスが少なくとも3つの異なる色を使用する（適切な）頂点彩色である。同様に、スター彩色では、任意の2色の頂点によって形成される誘導部分グラフは、スターグラフである連結成分を持つ。スター彩色はGrünbaum (1973)によって導入された。Gのスター彩色数は、Gをスター彩色するために必要な最小の色数である。
スターカラーリングの一般化の一つに、密接に関連する非巡回カラーリングの概念があります。非巡回カラーリングでは、すべてのサイクルで少なくとも3色を使用する必要があるため、2色誘導サブグラフはフォレストになります。グラフGの非巡回彩色数を で表すと となり、実際、Gのすべてのスターカラーリングは非巡回カラーリングです。
スター彩色数は、Nešetřil & Ossona de Mendez (2003) によって、すべての真小閉類上で有界であることが証明されました。この結果は、Nešetřil & Ossona de Mendez (2006) によってさらに一般化され、すべての低木深彩色に適用されました（標準彩色とスター彩色は、それぞれパラメータ1と2を持つ低木深彩色です）。
複雑
Albertsonら(2004)は、Gが平面かつ二部グラフであっても、かどうかを判定することはNP完全であると実証した。ColemanとMoré(1984)は、 Gが二部グラフであっても、最適なスターカラーリングを見つけることはNP困難であることを示した。
参考文献
- Albertson, Michael O.; Chappell, Glenn G.; Kierstead, Hal A.; Kündgen, André; Ramamurthi, Radhika (2004)「2色P4を含まない色付け」、The Electronic Journal of Combinatorics、11 (1)、doi : 10.37236/1779、MR 2056078。
- コールマン、トーマス F. ; モレ、ホルヘ (1984)、「疎ヘッセ行列の推定とグラフ彩色問題」(PDF)、数理計画法、28 (3): 243– 270、doi : 10.1007/BF02612334、hdl : 1813/ 6374 、MR 0736293。
- Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004)「グラフのスターカラーリング」、Journal of Graph Theory、47 (3): 163– 182、doi :10.1002/jgt.20029、MR 2089462。
- グリュンバウム、ブランコ（1973）、「平面グラフの非巡回着色」、イスラエル数学ジャーナル、14（4）：390–408、doi：10.1007/BF02764716、MR 0317982。
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2003)、「Colorings and homomorphisms of minor closed classes」、Discrete & Computational Geometry: The Goodman-Pollack Festschrift、Algorithms & Combinatorics、vol. 25、Springer-Verlag、pp. 651– 664、MR 2038495。
- Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2006)、「木の深さ、部分グラフの色付け、および準同型性境界」、European Journal of Combinatorics、27 (6): 1022– 1041、doi :10.1016/j.ejc.2005.01.010、MR 2226435。
外部リンク
- スターカラーリングと非環式カラーリング（1973）、イリノイ大学大学院生研究体験会（REGS）2008年発表。