Звёздная раскраска

Звёздное хроматическое число графа Дика равно 4, в то время как его хроматическое число равно 2.

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

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

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

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

Было показаноШаблон:Sfn, что проверка выполнения неравенства ${\chi }_s(G)⩽3$, является NP-полной задачей, даже если граф $G$ одновременно и планарен, и двудолен. Коулмэн и МорэШаблон:Sfn показали, что поиск оптимальной звёздной раскраски является NP-трудной задачей, даже если $G$ является двудольным графом.

Литература

• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Книга.
• Шаблон:Статья.

Ссылки

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