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

Материал из testwiki
Перейти к навигации Перейти к поиску

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

Примечания

Шаблон:Примечания

Литература

  1. ↑ Шаблон:Sfn0, гипотезу выдвинули Балог, Кохол, Плугар и Ю (Шаблон:Sfn0). Результат Гонкалвеса является улучшением результата Нэш-Вилльямса (Шаблон:Sfn0), затем Балога, Кохола, Плугара и Ю (Шаблон:Sfn0).
  2. ↑ 2,0 2,1 Вытекает из результатов Нэш-Вилльямса (Шаблон:Sfn0).
  3. ↑ Вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (Шаблон:Sfn0), результат которого улучшили Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0), затем Кляйтман (Шаблон:Sfn0).
  4. ↑ Доказали Ванг и Занг (Шаблон:Sfn0) и (независимо) вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (Шаблон:Sfn0), которые улучшили Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0) для обхвата 11, а затем Басса, Бёрнс, Кэмпбелл и др. (Шаблон:Sfn0) для обхвата 10 и Бородин, Косточка, Шейх и Ю (Шаблон:Sfn0) для обхвата 9.
  5. ↑ (Шаблон:Sfn0), хотя это явно в статье и не утверждается.
  6. ↑ Бородин, Иванова, Косточка, Шейх (Шаблон:Sfn0), которые улучшили результат Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0), а также предыдущий результат (Шаблон:Sfn0).
  7. ↑ Доказали Гуан и Зу без явного указания результата (Шаблон:Sfn0).
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=(a,_b)-разложение&oldid=18843