Ациклическая предписанная 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.