Arboricidad
La arboricidad de un gráfico no dirigido es el número mínimo de bosques en los que se pueden dividir sus bordes.
El teorema de Nash-Williams proporciona condiciones necesarias y suficientes para cuando un gráfico es k-arbórico.
La figura muestra el grafo bipartito completo K4,4, con los colores indicando una partición de sus aristas en tres bosques.
K4,4 no se puede dividir en menos bosques, porque cualquier bosque en sus ocho vértices tiene como máximo siete aristas, mientras que el gráfico general tiene dieciséis aristas, más del doble de la cantidad de aristas en un solo bosque.
Con más detalle, como cualquier bosque de
Nash-Williams demostró que estos dos hechos se pueden combinar para caracterizar la arboricidad: si n S y m S denotan el número de vértices y aristas, respectivamente, de cualquier subgrafo S del gráfico dado, entonces la arboricidad del gráfico es igual
aristas, de donde se sigue por la fórmula de Nash-Williams que los gráficos planos tienen arboricidad como máximo tres.
Como consecuencia, la arboricidad se puede calcular mediante un algoritmo de tiempo polinomial (Gabow y Westermann, 1992).
El mejor algoritmo exacto actual calcula la arboricidad en
Las aproximaciones a la arboricidad de un gráfico se pueden calcular más rápido.
[4] La anarboricidad de un gráfico es el número máximo de subgráficos no acíclicos disjuntos en los bordes en los que se pueden dividir los bordes del gráfico.
La arboricidad de la estrella de un gráfico es el tamaño del bosque mínimo, cada árbol del cual es una estrella (árbol con un máximo de un nodo sin hoja), en el que se pueden dividir los bordes del gráfico.
Si un árbol no es una estrella en sí mismo, su arboricidad de estrellas es dos, como se puede ver dividiendo los bordes en dos subconjuntos a distancias pares e impares de la raíz del árbol, respectivamente.
Por lo tanto, la arboricidad de la estrella de cualquier gráfico es al menos igual a la arboricidad, y como máximo igual al doble de la arboricidad.
La arboricidad lineal de un gráfico está estrechamente relacionada con su grado máximo y su número de pendiente.
De manera equivalente, es la relación máxima de aristas a vértices en cualquier subgrafo del gráfico, redondeado a un número entero.
Al igual que con la arboricidad, la pseudoarboricidad tiene una estructura matroide que le permite ser computada eficientemente (Gabow y Westermann, 1992).
Como cualquier gráfico plano tiene arboricidad tres, el grosor de cualquier gráfico es al menos igual a un tercio de la arboricidad y como máximo igual a la arboricidad.
La degeneración de un gráfico es el máximo, sobre todos los subgráficos inducidos del gráfico, del grado mínimo de un vértice en el subgráfico.
El número de coloración de un gráfico, también conocido como número de Szekeres-Wilf (Szekeres y Wilf, 1968), siempre es igual a su degeneración más 1 (Jensen y Toft, 1995, p. 77f.)).
Los dos parámetros han sido estudiados juntos por Tutte y Nash-Williams.
La arboricidad aparece en la conjetura de Goldberg-Seymour.
