星の塗り絵

数学のグラフ理論の分野において、グラフGのスター彩色とは、4 つの頂点上のすべてのパスが少なくとも 3 つの異なる色を使用する(適切な)頂点彩色です。同様に、スター彩色では、任意の 2 色の頂点によって形成される誘導サブグラフには、スター グラフである連結成分があります。スター彩色は、Grünbaum (1973 )によって導入されました。Gのスター彩色数⁠ ⁠は、 G をスター彩色するために必要な最小の色数です。 ${\displaystyle \chi _{s}(G)}$

スターカラーリングの一般化の 1 つは、密接に関連した非巡回カラーリングの概念です。非巡回カラーリングでは、すべてのサイクルで少なくとも 3 つの色を使用する必要があるため、2 色で誘導されるサブグラフはフォレストになります。グラフGの非巡回彩色数を⁠ ⁠${\displaystyle \chi _{a}(G)}$で表すと⁠ ⁠${\displaystyle \chi _{a}(G)\leq \chi _{s}(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 困難であることを示しました。 ${\displaystyle \chi _{s}(G)\leq 3}$

• 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)、「マイナー閉クラスのカラーリングと準同型」、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 年。