Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета. Эквивалентное определение — это такая раскраска, при которой любые компоненты связности порождённых подграфов, образованных вершинами любых двух цветов, являются звёздами. Звёздная раскраска была предложена Грюнбаумом.
Звёздное хроматическое число графа — это минимальное число цветов, необходимых для получения звёздной раскраски .
Одно из обобщений звёздной раскраски тесно связано с концепцией ациклической раскраски графа, в которой требуется, чтобы любой цикл использовал по меньшей мере три цвета, так что порождённые парой цветов подграфы образуют леса. Хроматическое число графа не превосходит звёздное хроматическое число , что фактически означает, что любая звёздная раскраска графа является ациклической раскраской.
Доказано, что звёздное хроматическое число ограничено для любого минорно замкнутого класса. Этот результат позднее был обобщён для всех раскрасок с малой древовидной глубиной (обычная раскраска и звёздная раскраска являются раскрасками с малой древовидной глубиной с параметрами 1 и 2 соответственно).
Было показано, что проверка выполнения неравенства , является NP-полной задачей, даже если граф одновременно и планарен, и двудолен. Коулмэн и Морэ показали, что поиск оптимальной звёздной раскраски является NP-трудной задачей, даже если является двудольным графом.
Примечания
Литература . . . . . .
Ссылки Star colorings and acyclic colorings (1973), статья на сайте Research Experiences for Graduate Students (REGS) университета штата Иллинойс, 2008.
Категория:Раскраска графа