Том 17, номер 2, 2010 г., Стр. 20-38

УДК 519.17
Бородин О. В.
Ациклическая 4-раскрашиваемость плоских графов, не содержащих 4- и 5-циклов

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

Ключевые слова: плоские графы, ациклическая раскраска, запрещённые циклы.

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

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