(a, b)-розклад

вид розбиття ребер графа

(ab)-Розклад неорієнтованого графа — це розбиття ребер на a + 1 множин, кожна з яких представляє ліс, за винятком однієї, степінь якої не перевищує b. Якщо цей граф теж є лісом, такий розклад називають F(ab)-розкладом.

Граф з деревністю a є (a, 0)-розкладаним. Будь-який (a, 0)-розклад або (a, 1)-розклад є F(a, 0)-розкладом або F(a, 1)-розкладом відповідно.

Класи графів ред.

  • Будь-який планарний граф є F(2, 4)-розкладаним[1]
  • Будь-який планарний граф   з обхватом щонайменше   є
    • F(2, 0)-розкладаним, якщо  [2];
    • (1, 4)-розкладаним, якщо  [3];
    • F(1, 2)-розкладаним, якщо  [4];
    • F(1, 1)-розкладаним, якщо  [5] або якщо будь-який цикл у   є або трикутником, або циклом з мінімум 8 ребрами, що не належать трикутнику[6];
    • (1, 5)-розкладним, якщо   не має 4-циклів[7].
  • Будь-який зовніпланарний граф є F(2, 0)-розкладаним[2] і (1, 3)-розкладаним[8].

Примітки ред.

  1. Gonçalves, 2009, гіпотезу висунули Балог, Кохол, Плугар і Ю (Balogh, Kochol, Pluhár, Yu, 2005). Результат Гонкалвеса покращує результат Неш-Вільямса (Nash-Williams, 1964), потім Балога, Кохола, Плугара і Ю (Balogh, Kochol, Pluhár, Yu, 2005).
  2. а б Випливає з результатів Неш-Вільямса (Nash-Williams, 1964).
  3. He, Hou, Lih, Shao та ін., 2002.
  4. Випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), результат якого покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), потім Кляйтман (Kleitman, 2008).
  5. Довели Ванг і Занг (Wang, Zhang, 2011) і (незалежно) випливає з результатів Монтасьє, Оссони де Мендез, Андре та Зу (Montassier, Ossona de Mendez, André, Zhu, 2012), які покращили Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002) для обхвату 11, а потім Басса, Бернс, Кемпбелл та ін. (Bassa, Burns, Campbell та ін., 2010) для обхвату 10 і Бородін, Косточка, Шейх і Ю (Borodin, Kostochka, Sheikh, Yu (a), 2008) для обхвату 9.
  6. (Borodin, Ivanova, Kostochka, Sheikh (b), 2009), хоча це явно в статті й не стверджується.
  7. Бородін, Іванова, Косточка, Шейх (Borodin, Ivanova, Kostochka, Sheikh (a), 2009), які покращили результат Хі, Ху, Лі, Шао та ін. (He, Hou, Lih, Shao та ін., 2002), а також попередній результат (Borodin, Kostochka, Sheikh, Yu (b), 2008).
  8. Довели Гуан та Зу без явного вказання результату (Guan, Zhu, 1999).

Література ред.