(a, b)-разложение неориентированного графа — это разбиение рёбер на a + 1 множеств, каждое из которых представляет лес, за исключением одного, имеющего степень, не превосходящую b. Если этот граф тоже является лесом, такое разложение называется F(a, b)-разложением.
Граф с древовидностью a является (a, 0)-разложимым. Любое (a, 0)-разложение или (a, 1)-разложение является a F(a, 0)-разложением или F(a, 1)-разложением соответственно.
Классы графов Любой планарный граф является F(2, 4)-разложимым, гипотезу выдвинули Балог, Кохол, Плугар и Ю (). Результат Гонкалвеса является улучшением результата Нэш-Вилльямса (), затем Балога, Кохола, Плугара и Ю (). Любой планарный граф с обхватом по меньшей мере является F(2, 0)-разложимым, если Вытекает из результатов Нэш-Вилльямса (). (1, 4)- разложимым, если . F(1, 2)- разложимым, если Вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (), результат которого улучшили Хи, Ху, Ли, Шао и др. (), затем Кляйтман ().. F(1, 1)- разложимым, если Доказали Ванг и Занг () и (независимо) вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (), которые улучшили Хи, Ху, Ли, Шао и др. () для обхвата 11, а затем Басса, Бёрнс, Кэмпбелл и др. () для обхвата 10 и Бородин, Косточка, Шейх и Ю () для обхвата 9. или если любой цикл является либо треугольником, либо циклом с минимум 8 рёбрами, не принадлежащими треугольнику(), хотя это явно в статье и не утверждается. (1, 5)- разложимым, если не имеет 4-цикловБородин, Иванова, Косточка, Шейх (), которые улучшили результат Хи, Ху, Ли, Шао и др. (), а также предыдущий результат (). Любой внешнепланарный граф является F(2, 0)-разложимым и (1, 3)- разложимымДоказали Гуан и Зу без явного указания результата ().
Примечания
Литература
Категория:Инварианты графов Категория:Объекты теории графов