Том 16, номер 5, 2009 г., Стр. 26-33

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

Аннотация:
Известно, что всякий плоский граф предписанно ациклически 7-раскрашиваем, и предполагается, что он предписанно ациклически 5-раскрашиваем (О. В. Бородин и др., 2002). Это предположение является совместным обобщением теорем Бородина об ациклической 5-раскраске (1979) и Томассена о предписанной 5-раскраске (1994). Однако до сих пор оно подтверждено лишь для некоторых узких классов плоских графов. Получен ряд достаточных условий ациклической 4- и 3-раскрашиваемости. В частности, плоские графы обхвата не менее 7 ациклически 3-раскрашиваемы (О. В. Бородин, A. В. Косточка и Вудал, 1999) и предписанно ациклически 3-раскрашиваемы (О. В. Бородин и др., 2009).
Естественной мерой разреженности плоского графа, введённой Эрдёшем и Стейнбергом, является отсутствие $k$-циклов, $4\le k\le S$. В работе доказано, что каждый плоский граф без циклов длины от 4 до 12 предписанно ациклически 3-раскрашиваем.
Библиогр. 18.

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

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

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