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