(a, b)-Розклад неорієнтованого графа — це розбиття ребер на a + 1 множин, кожна з яких представляє ліс, за винятком однієї, степінь якої не перевищує b. Якщо цей граф теж є лісом, такий розклад називають F(a, b)-розкладом.
Граф з деревністю a є (a, 0)-розкладаним. Будь-який (a, 0)-розклад або (a, 1)-розклад є 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)-розкладанимДовели Гуан та Зу без явного вказання результату ()..
Примітки
Література