descomposición ( a , b )

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

Un grafo con arboricidad a es ( a ,  0)-descomponible. Toda descomposición ( a , 0 ) o descomposición ( a , 1 ) es una descomposición F( a , 0 ) o una descomposición F( a , 1 ) respectivamente.    

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