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

Звёздное хроматическое число formula_1 графа formula_2 — это минимальное число цветов, необходимых для получения звёздной раскраски formula_2.

Одно из обобщений звёздной раскраски тесно связано с концепцией ациклической раскраски графа, в которой требуется, чтобы любой цикл использовал по меньшей мере три цвета, так что порождённые парой цветов подграфы образуют леса. Хроматическое число графа formula_4 не превосходит звёздное хроматическое число formula_1, что фактически означает, что любая звёздная раскраска графа formula_2 является ациклической раскраской.

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

Было показано, что проверка выполнения неравенства formula_7, является NP-полной задачей, даже если граф formula_2 одновременно и планарен, и двудолен.
Коулмэн и Морэ показали, что поиск оптимальной звёздной раскраски является NP-трудной задачей, даже если formula_2 является двудольным графом.
Звёздное хроматическое число [[Граф Дика|графа Дика]] равно 4, в то время как его хроматическое число равно 2.
UNK
Q131476
теории графов
Concept
Q504843
(правильная) раскраска вершин
Concept
Q917421
путь из четырёх вершин
Concept
Q2997928
компоненты связности
Concept
Q24743362
порождённых подграфов
Concept
Q2589168
звёздами
Concept
Q4677981
ациклической раскраски графа
UNK
Q272735
леса
Concept
Q7837500
глубиной деревьев
UNK
Q215206
NP-полной задачей
MISC
Q547823
планарен
Concept
Q174733
двудолен
Concept
Q628036
NP-трудной
MISC
Q7601205
Звёздная раскраска
UNK
Q7601205
Звёздная раскраска
UNK
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
studies