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

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

Примечания

^ Gonçalves (2009) , по предположению Балога и др. (2005) . Улучшение результатов Нэша-Вильямса (1964), а затем Балога и др. (2005) .
^ Перейти обратно: ^а ^б Подразумевается Нэш-Уильямсом (1964) .
^ Он и др. (2002)
^ Подразумевается Montassier et al. (2012) , улучшив результаты He et al. (2002) , затем Клейтман (2008) .
^ Независимо доказано Wang & Zhang (2011) и подразумевается Montassier et al. (2012) , улучшив результаты He et al. (2002) для обхвата 11, затем Bassa et al. (2010) для обхвата 10 и Бородин и др. (2008a) для обхвата 9.
^ Бородин и др. (2009b) , даже если это не указано явно.
^ Бородин и др. (2009a) , улучшая результаты He et al. (2002) , затем Бородин и др. (2008б) .
^ Доказано без явной ссылки Гуаном и Чжу (1999) .

Список литературы (хронологический порядок)

Нэш-Уильямс, Криспин Сент-Джон Алва (1964). «Разложение конечных графов на леса». Журнал Лондонского математического общества . 39 (1): 12. doi : 10.1112/jlms/s1-39.1.12 . МР 0161333 .
Гуан, диджей; Чжу, Сюдин (1999). «Игра хроматического числа внешнепланарных графов». Журнал теории графов . 30 (1): 67–70. doi : 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m .
Он, Вэньцзе; Хоу, Сяолин; Лих, Ко-Вэй; Шао, Цзиатин; Ван, Вэйфан; Чжу, Сюйдин (2002). «Ребро-разбиения планарных графов и их игровые числа раскрасок» . Журнал теории графов . 41 (4): 307–311. дои : 10.1002/jgt.10069 . S2CID 20929383 .
Балог, Йожеф; Кохол, Мартин; Плугар, Андраш; Ю, Синсин (2005). «Покрытие плоских графов лесами» . Журнал комбинаторной теории, серия B. 94 (1): 147–158. дои : 10.1016/j.ejc.2007.06.020 .
Бородин Олег Владимирович; Косточка Александр Владимирович; Шейх, Наим Н.; Ю, Гексин (2008). «Разложение плоского графа обхвата 9 на лес и паросочетание» . Европейский журнал комбинаторики . 29 (5): 1235–1241. дои : 10.1016/j.ejc.2007.06.020 .
Бородин Олег Владимирович; Косточка Александр Владимирович; Шейх, Наим Н.; Ты, Гексин (2008). « M -степени плоских графов без четырехугольников» (PDF) . Журнал теории графов . 60 (1): 80–8 CiteSeerX 10.1.1.224.8397 . дои : 10.1002/jgt.20346 . S2CID 7486622 .
Клейтман, Дэниел Дж. (2008). «Разбиение ребер планарного графа обхвата 6 на ребра леса и ребра набора непересекающихся путей и циклов». Рукопись .
Гонсалвес, Даниэль (2009). «Покрытие плоских графов лесами, имеющими ограниченную максимальную степень» . Журнал комбинаторной теории, серия B. 99 (2): 314–322. дои : 10.1016/j.jctb.2008.07.004 .
Бородин Олег Владимирович; Иванова Анна О.; Косточка Александр Владимирович; Шейх, Наим Н. (2009). «Разложение плоских графов без четырехугольников» (PDF) . Обсуждения Mathematicae Теория графов . 29 : 87–99. CiteSeerX 10.1.1.224.8787 . дои : 10.7151/dmgt.1434 .
Бородин Олег Владимирович; Иванова Анна О.; Косточка Александр Владимирович; Шейх, Наим Н. (2009). «Плоские графы, разложимые на лес и паросочетание» . Дискретная математика . 309 (1): 277–279. дои : 10.1016/j.disc.2007.12.104 .
Басса, А.; Бернс, Дж.; Кэмпбелл, Дж.; Дешпанде, А.; Фарли, Дж.; Хэлси, Л.; Хо, С.-Ю.; Клейтман, Д.; Михалакис, С.; Перссон, П.-О.; Пилявский, П.; Радемахер, Л.; Риль, А.; Риос, М.; Сэмюэл, Дж.; Теннер, BE; Виджаясарати, А.; Чжао, Л. (2010). «Разбиение планарного графа обхвата 10 на лес и сопоставление». Европейский журнал комбинаторики . 124 (3): 213–228. дои : 10.1111/j.1467-9590.2009.00468.x . S2CID 120663098 .
Ван, Инцянь; Чжан, Цицзюнь (2011). «Разложение плоского графа с обхватом не менее 8 на лес и паросочетание» . Дискретная математика . 311 (10–11): 844–849. дои : 10.1016/j.disc.2011.01.019 .
Монтасье, Микаэль; Оссона де Мендес, Патрис ; Андре, Распо; Чжу, Сюдин (2012). «Разложение графа на леса» . Журнал комбинаторной теории, серия B. 102 (1): 38–52. дои : 10.1016/j.jctb.2011.04.001 .

[1] Gonçalves (2009) , по предположению Балога и др. (2005) . Улучшение результатов Нэша-Вильямса (1964), а затем Балога и др. (2005) .

[NW-2] Перейти обратно: ^а ^б Подразумевается Нэш-Уильямсом (1964) .

[3] Он и др. (2002)

[4] Подразумевается Montassier et al. (2012) , улучшив результаты He et al. (2002) , затем Клейтман (2008) .

[5] Независимо доказано Wang & Zhang (2011) и подразумевается Montassier et al. (2012) , улучшив результаты He et al. (2002) для обхвата 11, затем Bassa et al. (2010) для обхвата 10 и Бородин и др. (2008a) для обхвата 9.

[6] Бородин и др. (2009b) , даже если это не указано явно.

[7] Бородин и др. (2009a) , улучшая результаты He et al. (2002) , затем Бородин и др. (2008б) .

[8] Доказано без явной ссылки Гуаном и Чжу (1999) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]