Espesor (teoría de grafos)

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

Por tanto, una gráfica plana tiene espesor 1. Las gráficas de espesor 2 se llaman gráficas biplanares . El concepto de espesor se origina en el problema Tierra-Luna sobre el número cromático de gráficos biplanares, planteado en 1959 por Gerhard Ringel , ^[4] y en una conjetura relacionada de 1962 de Frank Harary : Para cualquier gráfico de 9 puntos, ya sea en sí mismo o en sus El grafo complementario no es plano . El problema equivale a determinar si el gráfico completo K ₉ es biplanar (no lo es y la conjetura es cierta). ^[5] Petra Mutzel , Thomas Odenthal y Mark Scharbrodt escribieron un estudio exhaustivo ^[3] sobre el estado actual 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 el cual 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

Cada bosque es plano y cada gráfico plano se puede dividir en como máximo tres bosques. Por tanto, el espesor de cualquier gráfico G es como máximo igual a la arboricidad del mismo gráfico (el número mínimo de bosques en los que se puede dividir) y al menos igual a la arboricidad dividida por tres. ^{[2] [10]}

Las gráficas de grado máximo tienen espesor como máximo . ^[11] Esto no se puede mejorar: para un gráfico regular con una circunferencia de al menos , la circunferencia alta obliga a cualquier subgrafo plano a ser escaso, lo que hace que su grosor sea exactamente . ^[12] ${\displaystyle d}$ ${\displaystyle \lceil d/2\rceil }$ ${\displaystyle d}$ ${\displaystyle 2d}$ ${\displaystyle \lceil d/2\rceil }$

Mapa Tierra-Luna de nueve colores de Sulanke, con adyacencias descritas mediante la unión de un gráfico completo de 6 vértices y un gráfico de ciclo de 5 vértices (centro). Debido a que las adyacencias en este gráfico son la unión de aquellas en dos mapas planos (izquierda y derecha), tiene un espesor dos.

Los gráficos de espesor con vértices tienen como máximo aristas. Debido a que esto les da un grado promedio 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 los subgrafos del gráfico dado, del grado mínimo dentro del subgrafo. En la otra dirección, si un gráfico tiene degeneración, entonces su arboricidad y espesor son como máximo . Se puede encontrar un orden de los vértices del gráfico en el que cada vértice tiene como máximo vecinos que vienen después en el orden, y asignar estos bordes a subgrafos distintos produce una partición del gráfico en árboles, que son gráficos planos. ${\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 , se desconoce el valor preciso del número cromático; 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 planos 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 dibujos diferentes. Sin embargo, puede que no sea posible construir un dibujo de este tipo manteniendo los bordes dibujados como segmentos de línea recta .

Una invariante de gráfico diferente, el espesor rectilíneo o el espesor geométrico de un gráfico G , cuenta el número más pequeño de gráficos planos en los que G se puede descomponer sujeto a la restricción de que todos estos gráficos se pueden dibujar simultáneamente con bordes rectos. El grosor del libro añade una restricción adicional, que todos los vértices se dibujen en posición convexa , formando un diseño circular del gráfico. Sin embargo, a diferencia de lo que ocurre con 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 determinado y NP-completo probar si el espesor es como máximo dos. ^[16] Sin embargo, la conexión con la arboricidad permite aproximar el espesor dentro de una relación de aproximación de 3 en tiempo polinómico .

Referencias

1. Tutte, WT (1963), "El espesor de un gráfico", Indag. Matemáticas. , 66 : 567–577, doi : 10.1016/S1385-7258(63)50055-9 , SEÑOR  0157372.
2. , Petra ; Odenthal, Thomas; Scharbrodt, Mark (1998), "El espesor de los gráficos: una encuesta" (PDF) , Gráficos y combinatoria , 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 del gráfico, el espesor geométrico y los teoremas del separador, CCCG 2009, Vancouver, BC, 17 al 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 exterior y la arboricidad de un gráfico", Missouri J. Math. Ciencia. , 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 gráfico 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 gráfico bipartito completo", Proc. Filosofía de Cambridge. Soc. , 60 (1): 1–5, Bibcode :1964PCPS...60....1B, doi :10.1017/s0305004100037385, MR  0158388, S2CID  122829092.
10. Decano, Alice M.; Hutchinson, Joan P .; Scheinerman, Edward R. (1991), "Sobre el grosor y la arboricidad de un gráfico", Journal of Combinatorial Theory , Serie B, 52 (1): 147–151, doi :10.1016/0095-8956(91)90100-X , señor  1109429.
11. Halton, John H. (1991), "Sobre el grosor de los gráficos de un 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), "A 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, Señor  3930641
14. Latón, Peter; Cenek, Éowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna ; Mitchell, Joseph SB (2007), "Sobre incrustaciones simultáneas de gráficos planos", Computational Geometry , 36 (2): 117–130, doi : 10.1016/j.comgeo.2006.05.006 , MR  2278011.
15. Eppstein, David (2004), "Separando el espesor del espesor geométrico", Hacia una teoría de grafos geométricos , Contemp. Matemáticas, vol. 342, americano. Matemáticas. Soc., Providence, RI, págs. 75–86, arXiv : math/0204252 , doi : 10.1090/conm/342/06132, MR  2065254.
16. Mansfield, Anthony (1983), "Determinar el grosor de las gráficas es NP-difícil", Actas matemáticas de la Sociedad Filosófica de Cambridge , 93 (1): 9–23, Bibcode :1983MPCPS..93....9M, doi :10.1017/S030500410006028X, SEÑOR  0684270, S2CID  122028023.