(a, b) -descomposición

En teoría de grafos , la descomposición ( a ,  b ) de un grafo no dirigido es una partición de sus aristas en conjuntos a  + 1, cada uno de los cuales induce un bosque, excepto uno que induce un grafo con grado máximo  b . Si este gráfico también es un bosque, entonces lo llamamos descomposición F ( a ,  b ) .

Un gráfico con arboricidad a es ( a , 0) descomponible. Cada 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

• Cada gráfico plano es F (2, 4) -descomponible. ^[1]
• Cada gráfico plano con circunferencia al menos es ${\displaystyle G}$ ${\displaystyle g}$
  • F(2, 0) -descomponible si . ^[2] ${\displaystyle g\geq 4}$
  • (1, 4) -descomponible si . ^[3] ${\displaystyle g\geq 5}$
  • F(1, 2) -descomponible si . ^[4] ${\displaystyle g\geq 6}$
  • F(1, 1) -descomponible si , ^[5] o si cada ciclo de es un triángulo o un ciclo con al menos 8 aristas que no pertenecen a un triángulo. ^[6] ${\displaystyle g\geq 8}$ ${\displaystyle G}$
  • (1, 5) -descomponible si no tiene 4 ciclos. ^[7] ${\displaystyle G}$
• Cada gráfico plano exterior es descomponible F (2, 0) ^[2] y (1, 3). ^[8]

Notas

1. Gonçalves (2009), conjeturada por Balogh et al. (2005). Mejorando los resultados por Nash-Williams (1964) y luego Balogh et al. (2005).
2. Implicado por Nash-Williams (1964).
3. Él y otros. (2002)
4. Implicado por Montassier et al. (2012), mejorando los resultados de He et al. (2002), luego Kleitman (2008).
5. Probado de forma independiente por Wang y Zhang (2011) e implícito por Montassier et al. (2012), mejorando los resultados de He et al. (2002) para la circunferencia 11, luego Bassa et al. (2010) para la circunferencia 10 y Borodin et al. (2008a) para la circunferencia 9.
6. Borodin y col. (2009b), aunque no se indique explícitamente.
7. Borodin y col. (2009a), mejorando los resultados de He et al. (2002), luego Borodin et al. (2008b).
8. Probado sin referencia explícita por Guan & Zhu (1999).

Referencias (orden cronológico)

• Nash-Williams, Crispin St. John Alvah (1964). "Descomposición de grafos finitos en bosques". Revista de la Sociedad Matemática de Londres . 39 (1): 12. doi :10.1112/jlms/s1-39.1.12. SEÑOR  0161333.
• Guan, DJ; Zhu, Xuding (1999). "Juego de número cromático de gráficos planos exteriores". Revista de teoría de grafos . 30 (1): 67–70. doi :10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
• Él, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). "Particiones de bordes de gráficos planos y sus números de coloración del juego". Revista de teoría de grafos . 41 (4): 307–311. doi : 10.1002/jgt.10069 . S2CID  20929383.
• Balogh, József; Kochol, Martín; Pluhár, András; Yu, Xingxing (2005). "Cubrir gráficos planos con bosques". Revista de teoría combinatoria, serie B. 94 (1): 147-158. doi : 10.1016/j.ejc.2007.06.020 .
• Borodin, Oleg V.; Kostochka, Alexandr V.; Jeque, Naeem N.; Yu, Gexin (2008). "Descomponer un gráfico plano con circunferencia 9 en un bosque y una coincidencia". Revista europea de combinatoria . 29 (5): 1235-1241. doi : 10.1016/j.ejc.2007.06.020 .
• Borodin, Oleg V.; Kostochka, Alexandr V.; Jeque, Naeem N.; Yu, Gexin (2008). "M-grados de gráficos planos sin cuadrángulos" (PDF) . Revista de teoría de grafos . 60 (1): 80–85. CiteSeerX  10.1.1.224.8397 . doi :10.1002/jgt.20346. S2CID  7486622.
• Kleitman, Daniel J. (2008). "División de los bordes de un gráfico plano de circunferencia 6 en los de un bosque y los de un conjunto de ciclos y caminos disjuntos". Manuscrito .
• Gonçalves, Daniel (2009). "Cubriendo gráficos planos con bosques, uno de los cuales tiene un grado máximo acotado". Revista de teoría combinatoria, serie B. 99 (2): 314–322. doi : 10.1016/j.jctb.2008.07.004 .
• Borodin, Oleg V.; Ivanova, Anna O.; Kostochka, Alexandr V.; Jeque, Naeem N. (2009). "Descomposiciones de gráficos planos sin cuadrángulos" (PDF) . Discusiones Mathematicae Teoría de grafos . 29 : 87–99. CiteSeerX  10.1.1.224.8787 . doi :10.7151/dmgt.1434.
• Borodin, Oleg V.; Ivanova, Anna O.; Kostochka, Alexandr V.; Jeque, Naeem N. (2009). "Gráficos planos descomponibles en un bosque y un emparejamiento". Matemáticas discretas . 309 (1): 277–279. doi : 10.1016/j.disc.2007.12.104 .
• Bassa, A.; Quemaduras, 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.; Ríos, M.; Samuel, J.; Tenner, SER; Vijayasarathy, A.; Zhao, L. (2010). "División de un gráfico plano de circunferencia 10 en un bosque y una coincidencia". Revista europea de combinatoria . 124 (3): 213–228. doi :10.1111/j.1467-9590.2009.00468.x. S2CID  120663098.
• Wang, Yingqian; Zhang, Qijun (2011). "Descomponer un gráfico plano con una circunferencia de al menos 8 en un bosque y una coincidencia". Matemáticas discretas . 311 (10–11): 844–849. doi : 10.1016/j.disc.2011.01.019 .
• Montassier, Mickaël; Ossona de Méndez, Patrice ; André, Raspaud; Zhu, Xuding (2012). "Descomponer un gráfico en bosques". Revista de teoría combinatoria, serie B. 102 (1): 38–52. doi : 10.1016/j.jctb.2011.04.001 .