"Записки научных семинаров ПОМИ"
Том 543, стр. 119-125
Списочная вершинная древесность графа: аналог теоремы Бородина о $d$-раскрасках
Д. В. Карпов
С.-Петербургское
отделение Математического института
им. В А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
В работе доказан аналог теоремы Бородина о $d$-раскрасках для древесности.
Раскраска вершин графа -- {\em древесная}, если индуцированный подграф
на вершинах каждого из цветов ациклический.
Назовем связный граф $G$ {\em четным деревом Галлаи}, если каждый его блок
-- простой цикл или полный граф на нечетном количестве вершин.
Назовем $L = \{L(v)\}_{v\in V(G)}$ {\em $d/2$-списком}, если
$|L(v)|\ge {d_G(v)/2}$ для любой вершины $v$.
В работе доказано, что если связный граф не является четным деревом Галлаи,
то он имеет древесную раскраску в цвета любого $d/2$-списка.
Библ. -- 9 назв.
- Ключевые слова: вершинная древесность, списочная древесность, $d$-раскраски
[vertex arboricity, list arboricity, $d$-colorings]
Полный текст(.pdf)