Espesor (teoría de grafos)

En teoría de grafos , el grosor de un grafo G es el número mínimo de grafos planos en los que se pueden dividir las aristas de G. Es decir, si existe una colección de k grafos planos, todos con el mismo conjunto de vértices, de modo que la unión de estos grafos planos es G , entonces el grosor de G es como máximo k . ^{[1] [2]} En otras palabras, el grosor de un grafo es el número mínimo de subgrafos planos cuya unión es igual al grafo G. ^[3 ]

Por lo tanto, un grafo plano tiene un espesor de uno. Los grafos de espesor de dos se denominan grafos biplanares . El concepto de espesor se origina en el problema Tierra-Luna sobre el número cromático de grafos biplanares, planteado en 1959 por Gerhard Ringel [ ^4] y en una conjetura relacionada de 1962 de Frank Harary : Todo grafo sobre nueve puntos o su grafo complementario es no plano . El problema es equivalente a determinar si el grafo completo K ₉ es biplanar (no lo es, y la conjetura es verdadera). ^[5] Petra Mutzel ^[3] , Thomas Odenthal y Mark Scharbrodt escribieron un estudio exhaustivo sobre el estado del arte del tema en 1998. ^[2]

El espesor del gráfico completo en n vértices, K _n , es

${\displaystyle \left\lfloor {\frac {n+7}{6}}\right\rfloor ,}$

excepto cuando n = 9, 10 para cuyo caso el espesor es tres. ^{[6] [7]}

Con algunas excepciones, el espesor de un gráfico bipartito completo K _a,b es generalmente: ^{[8] [9]}

${\displaystyle \left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .}$

Todo bosque es plano y todo grafo plano puede dividirse en tres bosques como máximo. Por lo tanto, el espesor de cualquier grafo G es como máximo igual a la arboricidad del mismo grafo (el número mínimo de bosques en los que puede dividirse) y como mínimo igual a la arboricidad dividida por tres. ^{[2] [10]}

Los grafos de grado máximo tienen un espesor como máximo . ^[11] Esto no se puede mejorar: para un grafo -regular con una circunferencia de al menos , la circunferencia alta obliga a cualquier subgrafo planar a ser disperso, lo que hace que su espesor sea exactamente . ^[12]${\estilo de visualización d}$${\displaystyle \lceil d/2\rceil }$${\estilo de visualización d}$${\estilo de visualización 2d}$${\displaystyle \lceil d/2\rceil }$

Los grafos de espesor con vértices tienen como máximo aristas. Como esto les da un grado medio menor que , su degeneración es como máximo y su número cromático es como máximo . Aquí, la degeneración se puede definir como el máximo, sobre subgrafos del grafo dado, del grado mínimo dentro del subgrafo. En la otra dirección, si un grafo tiene degeneración, entonces su arboricidad y espesor son como máximo . Se puede encontrar un ordenamiento de los vértices del grafo en el que cada vértice tiene como máximo vecinos que vienen después que él en el ordenamiento, y asignar estas aristas a subgrafos distintos produce una partición del grafo en árboles, que son grafos planares.${\estilo de visualización t}$${\estilo de visualización n}$${\displaystyle t(3n-6)}$${\estilo de visualización 6t}$${\estilo de visualización 6t-1}$${\estilo de visualización 6t}$${\estilo de visualización D}$${\estilo de visualización D}$${\estilo de visualización D}$${\estilo de visualización D}$${\estilo de visualización D}$

Incluso en el caso , el valor preciso del número cromático es desconocido; este es el problema Tierra-Luna de Gerhard Ringel . Un ejemplo de Thom Sulanke muestra que, para , se necesitan al menos 9 colores. ^[13]${\estilo de visualización t=2}$${\estilo de visualización t=2}$

El espesor está estrechamente relacionado con el problema de la incrustación simultánea . ^[14] Si dos o más gráficos planares comparten el mismo conjunto de vértices, entonces es posible incrustar todos estos gráficos en el plano, con los bordes dibujados como curvas, de modo que cada vértice tenga la misma posición en todos los diferentes dibujos. Sin embargo, puede que no sea posible construir dicho dibujo manteniendo los bordes dibujados como segmentos de línea recta .

Un invariante gráfico diferente, el espesor rectilíneo o espesor geométrico de un gráfico G , cuenta el número más pequeño de gráficos planares en los que G puede descomponerse sujeto a la restricción de que todos estos gráficos pueden dibujarse simultáneamente con bordes rectos. El espesor del libro agrega una restricción adicional, que todos los vértices deben dibujarse en posición convexa , formando una disposición circular del gráfico. Sin embargo, en contraste con la situación de la arboricidad y la degeneración, no hay dos de estos tres parámetros de espesor que estén siempre dentro de un factor constante entre sí. ^[15]

Es NP-difícil calcular el espesor de un gráfico dado, y NP-completo comprobar si el espesor es como máximo dos. ^[16] Sin embargo, la conexión con la arboricidad permite aproximar el espesor dentro de una razón de aproximación de 3 en tiempo polinomial .