Espesor (teoría de grafos)

Número de subgrafos planares que cubren un grafo

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]

Gráficos específicos

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 .}$

Propiedades

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] ${\displaystyle d}$ ${\displaystyle \lceil d/2\rceil }$ ${\displaystyle d}$ ${\displaystyle 2d}$ ${\displaystyle \lceil d/2\rceil }$

Mapa de la Tierra y la Luna en nueve colores de Sulanke, con adyacencias descritas por la unión de un gráfico completo de 6 vértices y un gráfico cíclico de 5 vértices (centro). Debido a que las adyacencias en este gráfico son la unión de las de dos mapas planos (izquierdo y derecho), tiene un grosor de dos.

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. ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle t(3n-6)}$ ${\displaystyle 6t}$ ${\displaystyle 6t-1}$ ${\displaystyle 6t}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle 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] ${\displaystyle t=2}$ ${\displaystyle t=2}$

Problemas relacionados

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]

Complejidad computacional

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 .

Referencias

1. Tutte, WT (1963), "El espesor de un grafo", Indag. Math. , 66 : 567–577, doi : 10.1016/S1385-7258(63)50055-9 , MR  0157372.
2. Mutzel, Petra ; Odenthal, Thomas; Scharbrodt, Mark (1998), "El grosor de los gráficos: una encuesta" (PDF) , Graphs and Combinatorics , 14 (1): 59–73, CiteSeerX 10.1.1.34.6528 , doi :10.1007/PL00007219, MR  1617664, S2CID  31670574 .
3. Christian A. Duncan, Sobre el espesor de grafos, el espesor geométrico y los teoremas del separador, CCCG 2009, Vancouver, BC, 17-19 de agosto de 2009
4. Ringel, Gerhard (1959), Färbungsprobleme auf Flächen und Graphen , Mathematische Monographien, vol. 2, Berlín: VEB Deutscher Verlag der Wissenschaften, MR  0109349
5. Mäkinen, Erkki; Poranen, Timo (2012), "Una bibliografía comentada sobre el espesor, el espesor externo y la arboricidad de un grafo", Missouri J. Math. Sci. , 24 (1): 76–87, doi : 10.35834/mjms/1337950501 , S2CID  117703458
6. Mutzel, Odenthal y Scharbrodt (1998), Teorema 3.2.
7. Alekseev, VB; Gončakov, VS (1976), "El espesor de un grafo completo arbitrario", Mat. Sb. , Nueva Serie, 101 (143): 212–230, Bibcode :1976SbMat..30..187A, doi :10.1070/SM1976v030n02ABEH002267, MR  0460162.
8. Mutzel, Odenthal y Scharbrodt (1998), Teorema 3.4.
9. Beineke, Lowell W. ; Harary, Frank ; Moon, John W. (1964), "Sobre el espesor del grafo bipartito completo", Proc. Cambridge Philos. Soc. , 60 (1): 1–5, Bibcode :1964PCPS...60....1B, doi :10.1017/s0305004100037385, MR  0158388, S2CID  122829092.
10. Dean, Alice M.; Hutchinson, Joan P .; Scheinerman, Edward R. (1991), "Sobre el espesor y la arboricidad de un grafo", Journal of Combinatorial Theory , Serie B, 52 (1): 147–151, doi :10.1016/0095-8956(91)90100-X, MR  1109429.
11. Halton, John H. (1991), "Sobre el espesor de grafos de grado determinado", Ciencias de la Información , 54 (3): 219–238, doi :10.1016/0020-0255(91)90052-V, MR  1079441
12. Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (2004), "Una nota sobre la conjetura de Halton", Ciencias de la información , 164 (1–4): 61–64, doi :10.1016/j.ins.2003.06.008, MR  2076570
13. Gethner, Ellen (2018), "Hasta la Luna y más allá", en Gera, Ralucca ; Haynes, Teresa W. ; Hedetniemi, Stephen T. (eds.), Teoría de grafos: conjeturas favoritas y problemas abiertos, II , Libros de problemas de matemáticas, Springer International Publishing, págs. 115–133, doi :10.1007/978-3-319-97686-0_11, ISBN 978-3-319-97684-6, Sr.  3930641
14. Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna ; Mitchell, Joseph SB (2007), "Sobre incrustaciones simultáneas de grafos planos", Computational Geometry , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR  2278011.
15. Eppstein, David (2004), "Separación del espesor del espesor geométrico", Towards a theory of geometry graphs (Hacia una teoría de grafos geométricos ), Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, págs. 75–86, arXiv : math/0204252 , doi :10.1090/conm/342/06132, ISBN 978-0-8218-3484-8, Sr.  2065254.
16. Mansfield, Anthony (1983), "Determinar el grosor de los grafos es NP-difícil", Mathematical Proceedings of the Cambridge Philosophical Society , 93 (1): 9–23, Bibcode :1983MPCPS..93....9M, doi :10.1017/S030500410006028X, MR  0684270, S2CID  122028023.