(a, b)-разложение

(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)-разложимым^[1]
• Любой планарный граф ${\displaystyle G}$ с обхватом по меньшей мере ${\displaystyle g}$ является
  • F(2, 0)-разложимым, если ${\displaystyle g\geqslant 4}$^[2]
  • (1, 4)- разложимым, если ${\displaystyle g\geqslant 5}$^[3].
  • F(1, 2)- разложимым, если ${\displaystyle g\geqslant 6}$^[4].
  • F(1, 1)- разложимым, если ${\displaystyle g\geqslant 8}$^[5] или если любой цикл ${\displaystyle G}$ является либо треугольником, либо циклом с минимум 8 рёбрами, не принадлежащими треугольнику^[6]
  • (1, 5)- разложимым, если ${\displaystyle G}$ не имеет 4-циклов^[7]
• Любой внешнепланарный граф является F(2, 0)-разложимым^[2] и (1, 3)- разложимым^[8]