Аннотация:
В работе доказан аналог теоремы Бородина о $d$-раскрасках для древесности. Раскраска вершин графа – древесная, если индуцированный подграф на вершинах каждого из цветов ациклический. Назовем связный граф $G$четным деревом Галлаи, если каждый его блок – простой цикл или полный граф на нечетном количестве вершин. Назовем $L = \{L(v)\}_{v\in V(G)}$$d/2$-списком, если $|L(v)|\ge {d_G(v)/2}$ для любой вершины $v$. В работе доказано, что если связный граф не является четным деревом Галлаи, то он имеет древесную раскраску в цвета любого $d/2$-списка. Библ. – 9 назв.
Полный текст:
PDF файл (264 kB)