(a, b)-descomposición

Una descomposición ( a , b ) de un grafo no dirigido es una partición de aristas en conjuntos a + 1, cada uno de los cuales representa un bosque , excepto uno que tiene como máximo el grado b . Si este gráfico también es un bosque, tal descomposición se denomina descomposición F( a , b ) .

Un gráfico de árbol a es ( a , 0)-descomponible. Cualquier descomposición ( a , 0 ) o descomposición ( a , 1 ) es una descomposición F( a , 0 ) o una descomposición F( a , 1 ), respectivamente.

Clases de grafos

Cualquier gráfico plano es F(2, 4)-descomponible [1]
Cualquier gráfico plano con circunferencia al menos es $GRAMO$ $gramo$
- F(2, 0)-descomponible si
[2] ${\ Displaystyle g\ geqslant 4}$
(1, 4) - descomponible si [3] . ${\ Displaystyle g\ geqslant 5}$
F(1, 2) - descomponible si [4] . ${\ Displaystyle g\ geqslant 6}$
F(1, 1)-descomponible si [5] o si cualquier ciclo es un triángulo o un ciclo con al menos 8 aristas que no forman un triángulo [6] $g\geqslant 8$ $GRAMO$
(1, 5) - descomponible si no tiene 4 ciclos [7] $GRAMO$

Cualquier gráfico plano exterior es F(2, 0)-descomponible [2] y (1, 3)-descomponible [8]

Notas

↑ Gonçalves, 2009 , hipótesis de Balogh, Kochol, Pluhár, Yu, 2005 . El resultado de Goncalves es una mejora del resultado de Nash-Williams ( Nash-Williams, 1964 ), luego Balogh, Kochol, Pluhár, Yu, 2005 .
↑ 1 2 Sigue de los resultados de Nash-Williams ( Nash-Williams, 1964 ).
↑ He, Hou, Lih, Shao et al., 2002 .
↑ Se deriva de los resultados de Montassier, Ossona de Mendez, André y Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), cuyo resultado fue mejorado por He, Hu, Li, Shao et al.. ( He, Hou , Lih, Shao et al . ., 2002 ), luego Kleitman ( Kleitman, 2008 ).
↑ Probado por Wang y Zang ( Wang, Zhang, 2011 ) y (independientemente) se deriva de los resultados de Montassier, Ossona de Mendez, André y Zhu ( Montassier, Ossona de Mendez, André, Zhu, 2012 ), que mejoraron Chi, Hu, Li, Shao y otros ( He, Hou, Lih, Shao y otros, 2002 ) para la circunferencia 11, y luego Bassa, Burns, Campbell y otros ( Bassa, Burns, Campbell y otros, 2010 ) para la circunferencia 10 y Borodin, Kostochka, Sheikh y Yu ( Borodin, Kostochka, Sheikh, Yu (a), 2008 ) para la circunferencia 9.
↑ ( Borodin, Ivanova, Kostochka, Sheikh (b), 2009 ), aunque esto no se indica explícitamente en el artículo.
↑ Borodin, Ivanova, Kostochka, Sheikh ( Borodin, Ivanova, Kostochka, Sheikh (a), 2009 ), quienes mejoraron el resultado de Hee, Hu, Li, Shao et al. ( He, Hou, Lih, Shao et al., 2002 ), así como el resultado anterior ( Borodin, Kostochka, Sheikh, Yu (b), 2008 ).
↑ Probado por Guan y Zhu sin indicación explícita del resultado ( Guan, Zhu, 1999 ).

Literatura

San Crispín John Alvah Nash-Williams. Descomposición de grafos finitos en bosques // Diario de la Sociedad Matemática de Londres . - 1964. - T. 39 , núm. 1 . - S. 12 . -doi : 10.1112 / jlms/s1-39.1.12 .
Guan DJ, Zhu X. Número cromático del juego de gráficos de planos exteriores // Journal of Graph Theory. - 1999. - T. 30 , núm. 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. Particiones de borde de gráficos planares y sus números de coloración de juegos // 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. Cubriendo grafos planos con bosques // Journal of Combinatorial Theory, Serie B. - 2005. - V. 94 , no. 1 . — S. 147–158 . -doi : 10.1016/ j.ejc.2007.06.020 .
Daniel J. Kleitman. Partición de los bordes de un gráfico plano de circunferencia 6 en los de un bosque y los de un conjunto de caminos y ciclos disjuntos // Manuscrito. — 2008.
Daniel Gonçalves. Cubriendo grafos planos con bosques, uno con grado máximo acotado // Journal of Combinatorial Theory, Serie B. - 2009. - Vol. 99 , no. 2 . — Pág. 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. Particionamiento de un gráfico plano de circunferencia 10 en un bosque y un emparejamiento // European Journal of Combinatorics. - 2010. - T. 124 , núm. 3 . — Pág. 213–228 . doi : 10.1111 / j.1467-9590.2009.00468.x .
Yingqian Wang, Qijun Zhang. Descomposición de un gráfico plano con una circunferencia de al menos 8 en un bosque y una coincidencia // Matemáticas discretas. - 2011. - T. 311 , núm. 10-11 . — S. 844–849 . -doi : 10.1016/ j.disco.2011.01.019 .
Mickaël Montassier, Patrice Ossona de Méndez, Raspaud André, Xuding Zhu. Descomposición de un gráfico en bosques // Journal of Combinatorial Theory, Serie B. - 2012. - Vol. 102 , no. 1 . — Pág. 38–52 . -doi : 10.1016/ j.jctb.2011.04.001 .