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