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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

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

Граф з деревністю a є (a, 0)-розкладаним. Будь-який (a, 0)-розклад або (a, 1)-розклад є 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://uk.wiki.beta.math.wmflabs.org/w/index.php?title=(a,_b)-розклад&oldid=10205