Том 16, номер 6, 2009 г., Стр. 3-11

УДК 519.172
О. В. Бородин
Ациклическая 4-раскрашиваемость плоских графов без циклов длины 4 и 6

Аннотация:
Известно, что всякий плоский граф ациклически 5-раскрашиваем (О. В. Бородин, 1976), причём эта оценка неулучшаема. Получен также ряд достаточных условий ациклической 4-раскрашиваемости. В частности, ациклическая 4-раскрашиваемость доказана для следующих плоских графов: не содержащих 3- и 4-циклов (О. В. Бородин, А. В. Косточка и Вудал, 1999), без циклов длины 4, 5 и 6 (Монтасьер, Распо и Ванг, 2006), без 4-, 6- и 7-циклов, а также без циклов длины 4, 6 и 8 (Чен, Распо и Ванг, 2009). В данной работе доказано, что всякий плоский граф, не содержащий 4- и 6-циклов, ациклически 4-раскрашиваем.
Библиогр. 17.

Ключевые слова: плоский граф, aциклическая раскраска, предписанная aциклическая раскраска.

Бородин Олег Вениаминович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: brdnoleg@math.nsc.ru

Статья поступила 13 мая 2009 г.
Исправленный вариант — 17 июня 2009 г.