(a, b)-descompunere
O descompunere ( a , b ) a unui graf nedirecționat este o împărțire a muchiilor în a + 1 mulțimi, fiecare dintre acestea reprezentând o pădure , cu excepția uneia care are gradul cel mult b . Dacă acest grafic este și o pădure, o astfel de descompunere se numește descompunere F( a , b ) .
Un grafic arbore a este ( a , 0)-descompunebil. Orice descompunere ( a , 0 ) sau descompunere ( a , 1 ) este o descompunere F( a , 0 ) sau, respectiv, o descompunere F( a , 1 ).
Clasele grafice
- Orice graf plan este F(2, 4)-descompunebil [1]
- Orice grafic plan cu cel puțin circumferință este
- F(2, 0)-descompunebil dacă
[2]
- (1, 4) - descompunebil dacă [3] .
- F(1, 2) - descompunebil dacă [4] .
- F(1, 1)-descompunebil dacă [5] sau dacă orice ciclu este fie un triunghi, fie un ciclu cu cel puțin 8 muchii nu într-un triunghi [6]
- (1, 5) - descompunebil dacă nu are 4-cicluri [7]
Orice grafic exterior planar este F(2, 0)-descomposabil [2] și (1, 3)-descomposabil [8]
Note
- ↑ Gonçalves, 2009 , ipotezată de Balogh, Kochol, Pluhár, Yu, 2005 . Rezultatul lui Goncalves este o îmbunătățire față de rezultatul lui Nash-Williams ( Nash-Williams, 1964 ), apoi Balogh, Kochol, Pluhár, Yu, 2005 .
- ↑ 1 2 Urmează din rezultatele lui Nash-Williams ( Nash-Williams, 1964 ).
- ↑ He, Hou, Lih, Shao et al., 2002 .
- ↑ Urmează din rezultatele lui Montassier, Ossona de Mendez, André și Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), al căror rezultat a fost îmbunătățit de He, Hu, Li, Shao și colab. ( He, Hou , Lih, Shao şi colab., 2002 ), apoi Kleitman ( Kleitman, 2008 ).
- ↑ Dovedit de Wang și Zang ( Wang, Zhang, 2011 ) și (independent) rezultă din rezultatele lui Montassier, Ossona de Mendez, André și Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), care au îmbunătățit Chi, Hu, Li, Shao și colab. ( He, Hou, Lih, Shao și colab., 2002 ) pentru circumferința 11, iar apoi Bassa, Burns, Campbell și colab. ( Bassa, Burns, Campbell și colab., 2010 ) pentru circumferință 10 și Borodin, Kostochka, Sheikh și Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) pentru circumferința 9.
- ↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), deși acest lucru nu este menționat în mod explicit în articol.
- ↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), care au îmbunătățit rezultatul lui Hee, Hu, Li, Shao și colab. ( He, Hou, Lih, Shao și colab., 2002 ), precum și rezultatul anterior ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
- ↑ Dovedit de Guan și Zhu fără indicarea explicită a rezultatului ( Guan, Zhu, 1999 ).
Literatură
- Crispin St. John Alvah Nash-Williams. Descompunerea graficelor finite în păduri // Journal of the London Mathematical Society . - 1964. - T. 39 , nr. 1 . - S. 12 . - doi : 10.1112/jlms/s1-39.1.12 .
- Guan DJ, Zhu X. Numărul cromatic al jocului de grafice exterioare // Journal of Graph Theory. - 1999. - T. 30 , nr. 1 . — S. 67–70 . - doi : 10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m .
- Wenjie He, Xiaoling Hou, Ko-Wei Lih, Jiating Shao, Weifan Wang, Xuding Zhu. Partiții de margine ale graficelor plane și numerele lor de colorare a jocului // Journal of Graph Theory. - 2002. - T. 41 . — S. 307–311 . - doi : 10.1002/jgt.10069 .
- József Balogh, Martin Kochol, András Pluhár, Xingxing Yu. Acoperirea graficelor plane cu păduri // Journal of Combinatorial Theory, Seria B. - 2005. - V. 94 , nr. 1 . — S. 147–158 . - doi : 10.1016/j.ejc.2007.06.020 .
- Daniel J. Kleitman. Împărțirea marginilor unei circumferințe 6 Grafic plan în cele ale unei păduri și cele ale unui set de căi și cicluri disjunctive // Manuscris. — 2008.
- Daniel Goncalves. Acoperirea grafurilor plane cu păduri, unul având gradul maxim mărginit // Journal of Combinatorial Theory, Seria B. - 2009. - Vol. 99 , nr. 2 . — S. 314–322 . - doi : 10.1016/j.jctb.2008.07.004 .
- Bassa A., Burns J., Campbell J., Deshpande A., Farley J., Halsey L., Ho S.-Y., Kleitman, D., Michalakis S., Persson P.-O., Pylyavskyy P. , Rademacher L., Riehl, A., Rios M., Samuel J., Tenner BE, Vijayasarathy A., Zhao L. Partitioning a Planar Graph of Girth 10 into a Forest and a Matching // European Journal of Combinatorics. - 2010. - T. 124 , nr. 3 . — S. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
- Yingqian Wang, Qijun Zhang. Descompunerea unui grafic plan cu circumferința de cel puțin 8 într-o pădure și o potrivire // Matematică discretă. - 2011. - T. 311 , nr. 10-11 . — S. 844–849 . - doi : 10.1016/j.disc.2011.01.019 .
- Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu. Descompunerea unui grafic în păduri // Journal of Combinatorial Theory, Seria B. - 2012. - Vol. 102 , nr. 1 . — S. 38–52 . - doi : 10.1016/j.jctb.2011.04.001 .