Звёздная раскраска ({f~[;ugx jgvtjgvtg)

Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом^[1].

Звёздное хроматическое число $\chi _{s}(G)$ графа $G$ — это минимальное число цветов, необходимых для получения звёздной раскраски $G$ .

Одно из обобщений звёздной раскраски тесно связано с концепцией ациклической раскраски графа, в которой требуется, чтобы любой цикл использовал по меньшей мере три цвета, так что порождённые парой цветов подграфы образуют леса. Хроматическое число графа $\chi _{a}(G)$ не превосходит звёздное хроматическое число $\chi _{s}(G)$ , что фактически означает, что любая звёздная раскраска графа $G$ является ациклической раскраской.

Доказано, что звёздное хроматическое число ограничено для любого минорно замкнутого класса^[2]. Этот результат позднее был обобщён ^[3] для всех раскрасок с малой глубиной деревьев (обычная раскраска и звёздная раскраска являются раскрасками с малой глубиной деревьев с параметрами 1 и 2 соответственно).

Было показано^[4], что проверка выполнения неравенства $\chi _{s}(G)\leqslant 3$ , является NP-полной задачей, даже если граф $G$ одновременно и планарен, и двудолен. Коулмэн и Морэ^[5] показали, что поиск оптимальной звёздной раскраски является NP-трудной задачей, даже если $G$ является двудольным графом.

Литература

Michael O. Albertson, Glenn G. Chappell, Hal A. Kierstead, André Kündgen, Radhika Ramamurthi. Coloring with no 2-Colored P₄'s // The Electronic Journal of Combinatorics. — 2004. — Т. 11, вып. 1..
Thomas F. Coleman, Jorge Moré. Estimation of sparse Hessian matrices and graph coloring problems // Mathematical Programming. — 1984. — Т. 28, вып. 3. — С. 243–270. — doi:10.1007/BF02612334..
Guillaume Fertin, André Raspaud, Bruce Reed. Star coloring of graphs // Journal of Graph Theory. — 2004. — Т. 47, вып. 3. — С. 163–182. — doi:10.1002/jgt.20029..
Branko Grünbaum. Acyclic colorings of planar graphs // Israel Journal of Mathematics. — 1973. — Т. 14. — С. 390–408. — doi:10.1007/BF02764716..
Nešetřil Jaroslav, Ossona de Mendez Patrice. Discrete & Computational Geometry: The Goodman-Pollack Festschrift. — Springer-Verlag, 2003. — Т. 25. — С. 651–664. — (Algorithms & Combinatorics)..
Nešetřil Jaroslav, Ossona de Mendez Patrice. Tree depth, subgraph coloring and homomorphism bounds // European Journal of Combinatorics. — 2006. — Т. 27, вып. 6. — С. 1022–1041. — doi:10.1016/j.ejc.2005.01.010..

Ссылки

Star colorings and acyclic colorings (1973), статья на сайте Research Experiences for Graduate Students (REGS) университета штата Иллинойс, 2008.

[_2eb7240b73e38a4a-1] Грюнбаум, 1973.

[_117bb0b23ad29088-2] Нешетржил, Оссона, 2003.

[_15db91b3d9209869-3] Нешетржил, Оссона, 2006.

[_4173621f42dd7ad6-4] Альбертсон, 2004.

[_cf6beadebf5b1686-5] Коулмэн, Морэ, 1984.

[1]

[2]

[3]

[4]

[5]