En teoría de grafos , el acto de colorear generalmente implica la asignación de etiquetas a vértices , aristas o caras en un gráfico . La coloración de incidencia es un etiquetado de gráfico especial donde a cada incidencia de un borde con un vértice se le asigna un color bajo ciertas restricciones.
Definiciones
Debajo de G denota un gráfico simple con un conjunto de vértices no vacío (no vacío) V ( G ), un conjunto de bordes E ( G ) y un grado máximo Δ ( G ).
Definición. Una incidencia se define como un par ( v , e ) donde es un punto final de En palabras simples, se dice que el vértice v es incidente al borde e . Se dice que dos incidencias ( v , e ) y ( u , f ) son adyacentes o vecinas si se cumple una de las siguientes condiciones:
- v = u , e ≠ f
- e = f , v ≠ u
- e = { v , u }, f = { u , w } y v ≠ w .
Definición. Let Me ( G ) el conjunto de todas las incidencias de G . Una coloración de incidencia de G es una función que toma valores distintos en incidencias adyacentes (usamos la notación simplificada c ( v , u ) se usa en lugar de c (( v , e ))). El número mínimo de colores necesarios para la coloración de incidencia de un gráfico G se conoce como el número cromático de incidencia o el número de coloración de incidencia de G , representado porEsta notación fue introducida por Jennifer J. Quinn Massey y Richard A. Brualdi en 1993.
Historia
El concepto de coloración de incidencia fue introducido por Brualdi y Massey en 1993, quienes lo delimitaron en términos de Δ ( G ). Inicialmente se averiguó el número cromático de incidencia de árboles, gráficos bipartitos completos y gráficos completos. También conjeturaron que todos los gráficos pueden tener una coloración de incidencia usando Δ ( G ) + 2 colores (conjetura de coloración de incidencia - ICC). Esta conjetura fue refutada por Guiduli, quien demostró que el concepto de coloración por incidencia es un caso de arboricidad de estrellas dirigida, [1] introducido por Alon y Algor. Su contraejemplo mostró que el número cromático de incidencia es como máximo Δ ( G ) + O (log Δ ( G )). [2]
Chen y col. Se encontró la incidencia cromática del número de trayectorias , abanicos, ciclos , ruedas, gráfica tripartita completa y añadiendo ruedas de borde. Pocos años después, Shiu et al. mostró que esta conjetura es cierta para ciertas gráficas cúbicas como las gráficas cúbicas hamiltonianas. Mostró que en el caso de un gráfico plano exterior de grado máximo 4, el número cromático de incidencia no es 5. Los límites para el número cromático de incidencia de varias clases de gráficos se encuentran ahora.
Resultados basicos
- Proposición.
Prueba. Deje que v sea el vértice con Δ grado máximo en G . Dejarsean las aristas que inciden en el vértice v . Considerar Podemos ver que cada par de incidencias Δ + 1, es decir, es de buena vecindad. Por lo tanto, estas incidencias deben teñirse con colores distintos.
El límite se alcanza mediante árboles y gráficos completos:
- Si G es un gráfico completo con al menos dos vértices, entonces
- Si G es un árbol con al menos dos vértices, entonces
Los principales resultados fueron demostrados por Brualdi y Massey (1993). Shiu, Sun y Wu han propuesto ciertas condiciones necesarias para que el gráfico satisfaga
- El número cromático de incidencia del gráfico bipartito completo con m ≥ n ≥ 2, es m + 2.
- y
Coloración de incidencia de algunas clases de gráficos
Mallas
Se introducen varios algoritmos para proporcionar coloración de incidencia de mallas [3] como mallas cuadradas , mallas alveolares y mallas hexagonales. Estos algoritmos son óptimos. Para cada malla, los colores de incidencia se pueden hacer en el tiempo lineal con la menor cantidad de colores. Se ha comprobado que los colores ∆ ( G ) + 1 son necesarios para la coloración de incidencia de mallas cuadradas, mallas alveolares y mallas hexagonales.
- El número cromático de incidencia de una malla cuadrada es 5.
- El número cromático de incidencia de una malla hexagonal es 7.
- El número cromático de incidencia de una malla alveolar es 4.
Gráficos de Halin
Chen, Wang y Pang demostraron que si G es un gráfico de Halin con ∆ ( G )> 4 entoncesPara gráficos de Halin con ∆ ( G ) = 3 o 4, Jing-Zhe Qu mostróser 5 o 6 respectivamente. Si el número de coloración de incidencia de los gráficos de Halin con grado bajo es Δ ( G ) + 1 es todavía un problema sin resolver.
Shiu y Sun demostraron todos los gráficos de Halin cúbicos que no sean tiene una coloración de incidencia con Δ ( G ) + 2 colores. Su, Meng y Guo ampliaron este resultado a todos los gráficos pseudo-Halin.
Si el gráfico de Halin G contiene un árbol T , entonces[4]
gráficos k-degenerados
DL Chen, PCB Lam y WC Shiu habían conjeturado que el número cromático de incidencia de un gráfico cúbico G es como máximo ∆ ( G ) + 2. Lo demostraron para ciertos gráficos cúbicos como los gráficos cúbicos hamiltonianos. Con base en estos resultados, MH Dolama, E. Sopena y X. Zhu (2004) estudiaron las clases de grafos para las cualesestá acotado por ∆ ( G ) + c donde c es una constante fija. [5] Se dice que un gráfico se genera k si para cada subgrafo H de G , el grado mínimo de H es como máximo k .
- El número cromático de incidencia de los gráficos degenerados en k G es como máximo ∆ ( G ) + 2 k - 1.
- El número cromático de incidencia de K 4 gráficos libres menores G es como máximo ∆ ( G ) + 2 y forma un límite estrecho.
- El número cromático de incidencia de un gráfico plano G es como máximo ∆ ( G ) + 7.
Gráficos planos exteriores
Considere un grafo plano exterior G con vértice cortado v tal que G - v es la unión de y . Dejar (resp. ) ser el subgrafo inducido en el vértice v y los vértices de (resp. ). Luego es el máximo de y dónde es el grado de vértice v en G .
El número cromático de incidencia de un gráfico plano exterior G es como máximo ∆ ( G ) + 2. En el caso de gráficos planos exteriores con ∆ ( G )> 3, el número cromático de incidencia es ∆ ( G ) + 1.
Dado que las gráficas planas externas son gráficas libres de K 4 menores, aceptan una coloración de incidencia (Δ + 2, 2). [5] [6] La solución para el número cromático de incidencia del gráfico del plano exterior G que tiene Δ ( G ) = 3 y el gráfico del plano exterior conectado a 2 sigue siendo una cuestión abierta.
Anillos de cuerdas
Los anillos de cuerdas son variaciones de las redes de anillos. El uso de anillos cordales en la comunicación es muy extenso debido a sus ventajas sobre las redes de interconexión con topología en anillo y otras estructuras analizadas como mallas, hipercubos, grafos de Cayley, etc. Arden y Lee [7] propusieron por primera vez el anillo cordal de grado 3 , es decir, la red estructurada en anillo en la que cada nodo tiene un enlace adicional conocido como acorde, a algún otro nodo de la red. Las redes de bucles distribuidos son anillos de cuerdas de grado 4 que se construyen agregando 2 cuerdas adicionales en cada vértice de una red de anillos.
El anillo de cuerdas en N nodos y la longitud de cuerda d , denotado por CR ( N , d ), es un gráfico definido como:
Estos gráficos se estudian por su aplicación en comunicación. Kung-Fu Ding, Kung-Jui Pai y Ro-Yu Wu estudiaron la coloración de incidencia de los anillos de acordes. [8] Se formulan varios algoritmos para encontrar el número cromático de incidencia de anillos cordales. Los principales hallazgos son:
Potencias de ciclos
Keaitsuda Nakprasit y Kittikorn Nakprasit estudiaron la coloración de incidencia de las potencias de los ciclos, Si 2 k + 1 ≥ n entoncesasí que asume n > 2 k + 1 y escribe:
Sus resultados se pueden resumir de la siguiente manera: [9]
La relación con la conjetura de coloración de incidencia viene dada por la observación de que
Relación entre el número cromático de incidencia y el número de dominación de un gráfico
- Proposición. [10] Sea G una gráfica simple conectada de orden n , tamaño my número de dominación Luego
Prueba. Forme un dígrafo D ( G ) a partir del gráfico G dividiendo cada borde de G en 2 arcos en direcciones opuestas. Podemos ver que el número total de arcos en D ( G ) es 2 m . Según Guiduli, [2] la coloración de incidencia de G es equivalente a la coloración adecuada del dígrafo D ( G ), donde 2 arcos distintos y son adyacentes si se cumple una de las siguientes condiciones: (i) u = x ; (ii) v = x o y = u . Según la definición de adyacencia de arcos, un conjunto independiente de arcos en D ( G ) es un bosque de estrellas. Por lo tanto, un conjunto máximo de arcos independientes es un bosque estelar máximo . Esto implica que al menosSe requieren clases de color. [10]
Esta relación ha sido ampliamente utilizada en la caracterización de gráficos r -regulares coloreables de incidencia ( r + 1) . El resultado importante en colorante incidencia de r gráficos -Regular es: Si el gráfico G es r-Regular gráfico , entoncessi y solo si V ( G ) es una unión disjunta de r + 1 conjuntos dominantes . [10]
Intervalo de coloración de incidencia
Definición. Un subconjunto finitoes un intervalo si y solo si contiene todos los números entre su mínimo y su máximo.
Definición. Sea c una coloración de incidencia de G y defina
Una coloración de incidencia de intervalo de G es una coloración de incidencia c tal que para cada vértice v de G el conjuntoes un intervalo. [11] [12] La incidencia colorear número de intervalo de G es el número mínimo de colores utilizados para la incidencia intervalo de coloración de G . Se denota por Está claro que si solo los colores se utilizan para la coloración de incidencia de intervalo, entonces se dice que es mínima.
El concepto de coloración de incidencia de intervalo fue introducido por A. Malafiejska, R. Janczewski y M. Malafiejski. Ellos demostraronpara gráficos bipartitos. [13] En el caso de gráficos bipartitos regulares, se mantiene la igualdad. Los gráficos bipartitos subcúbicos admiten una coloración de incidencia de intervalo utilizando cuatro, cinco o seis colores. También han demostrado que la incidencia de 5 colores se puede decidir en tiempo lineal para gráficos bipartitos con ∆ ( G ) = 4.
Coloración de incidencia fraccionada
La versión fraccionada de la coloración incidencia fue introducido por primera vez por Yang en 2007. Un r tupla incidencia k -Coloreado de un gráfico G es la asignación de r colores a cada incidencia de gráfico G de un conjunto de k colores tales que las incidencias adyacentes se les dan conjuntos de colores inconexos. [14] Por definición, es obvio que el color k de incidencia de 1 tupla también es un color de incidencia k .
El número cromático de incidencia fraccional del gráfico G es el mínimo de las fraccionesde tal manera que G admite una r -tupla incidencia k- coloración. La coloración de incidencia fraccionada tiene grandes aplicaciones en varios campos de la informática. Basado en los resultados de coloración de incidencia de Guiduli, [2] Yang ha demostrado que el número cromático de incidencia fraccional de cualquier gráfico es como máximo Δ ( G ) + 20 log Δ ( G ) + 84. También ha demostrado la existencia de gráficos con número cromático de incidencia al menos Δ ( G ) + Ω (log Δ ( G )).
Desigualdad de Nordhaus-Gaddum
Sea G una gráfica con n vértices tal que dónde denota el complemento de G . Luego[10] Estos límites son nítidos para todos los valores de n .
Juego de colorear Incidencia
El juego de colorear Incidence fue introducido por primera vez por SD Andres. [15] Es la versión de incidencia del juego de colorear de vértices, en el que las incidencias de un gráfico se colorean en lugar de los vértices. El número cromático del juego de incidencia es el nuevo parámetro definido como un análogo de la teoría del juego del número cromático de incidencia.
El juego consiste en que dos jugadores, Alice y Bob, construyen un color de incidencia adecuado. Las reglas se establecen a continuación:
- Alice y Bob colorean las incidencias de una gráfica G con un conjunto k de colores.
- Se turnan para proporcionar una coloración adecuada a una incidencia incolora. Generalmente, comienza Alice.
- En el caso de una incidencia que no se puede colorear correctamente, Bob gana.
- Si todas las incidencias del gráfico están coloreadas correctamente, Alice gana.
El número cromático del juego de incidencia de un gráfico G , denotado por, es la menor cantidad de colores necesarios para que Alice gane en un juego de colorear de incidencia. Unifica las ideas de número cromático de incidencia de un gráfico y número cromático de juego en caso de un gráfico no dirigido. Andrés descubrió que el límite superior paraen el caso de gráficos k -degenerados es 2Δ + 4 k - 2. Este límite se mejoró a 2Δ + 3 k - 1 en el caso de gráficos en los que Δ es al menos 5 k . También se determina el número cromático del juego de incidencia de estrellas, ciclos y ruedas suficientemente grandes. [15] John Y. Kim (2011) ha averiguado el número cromático exacto del juego de incidencia de los grandes caminos y ha dado una prueba correcta de un resultado expresado por Andrés sobre el número cromático exacto del juego de incidencia de las ruedas grandes. [dieciséis]
Referencias
- ^ Algor I., Alon N. (1989); " La arboricidad estelar de los gráficos ", Discrete Mathematics 75, págs. 11-22.
- ↑ a b c Guiduli B. (1997); " Sobre la coloración de incidencia y la arboricidad de estrellas de los gráficos ", Discrete Mathematics 163, págs. 275-278
- ^ Huang, CI; Wang, YL; Chung, SS (2004), " La incidencia de colorear números de mallas ", Computadoras y matemáticas con aplicaciones 48, págs. 1643–1649
- ^ Wang, SD; Cheng, DL; Pang, SC (2002), " El número de coloración de incidencia de las gráficas de Halin y las gráficas planas externas ", Matemáticas discretas 256, págs. 397–405
- ↑ a b Hosseini Dolama, M .; Sopena, E .; Zhu, X. (2004), " Coloración de incidencia de gráficos generados por k ", Matemáticas discretas 283, págs. 121-128
- ^ Wang, S .; Xu, J .; Ma, F .; Xu, C. (2008), " El color de incidencia (Δ + 2, 2) de los gráficos planos externos ", Progress in Natural Science 18, págs. 575–578.
- ^ Arden BW, Lee H. (1981); " Análisis de la red de anillo cordal ", IEEE Transactions on Computers 30, págs. 291-295.
- ^ Ding KF, Pai KJ, Yu R. (1981); " Algunos resultados sobre la incidencia de coloración del número de anillos de cuerdas * ", 32º Taller de Matemática Combinatoria y Teoría de la Computación, págs. 89-93.
- ^ Nakprasit, K .; Nakprasit, K. (2012), "Colores de incidencia de las potencias de los ciclos ", Revista Internacional de Matemáticas Puras y Aplicadas 76 (1), págs. 143-148
- ^ a b c d Sun, PK (2012), " Coloración de incidencia de gráficos regulares y gráficos complementarios ", Taiwanese Journal of Mathematics 16, No. 6, págs. 2289–2295
- ^ Janczewski, R .; Malafiejska, A .; Malafiejski, M., "Interval Wavelength Assignment in All-Optical Star Networks", Parallel Processing and Applied Mathematics, 8th International Conference, PPAM 2009, Wtroclaw, Polonia, 13-16 de septiembre de 2009. Revised Selected Papers Part I (Springer), págs. 11-20, doi: 10.1007 / 978-3-642-14390-8_2, ISBN 978-3-642-14389-2
- ^ Janczewski, R .; Małafiejska, A .; Małafiejski, M. (2015), " Coloración del gráfico de incidencia de intervalo ", Matemáticas aplicadas discretas 182, págs. 73–83
- ^ Janczewski, R .; Małafiejska, A .; Małafiejski, M. (2014), " Coloración de incidencia de intervalo de gráficos bipartitos ", Matemáticas aplicadas discretas 166, págs. 131–145
- ^ Yang, D (2012), " Coloración de incidencia fraccionada y arboricidad en estrella de los gráficos ", Ars Combinatoria - Waterloo y luego Winnipeg 105, págs. 213-224
- ^ a b Andrés, SD (2009), " El número cromático del juego de incidencia ", Matemáticas aplicadas discretas 157, págs. 1980-1987
- ^ Kim, JY (2011), " El número cromático del juego de incidencia de caminos y subgrafos de ruedas ", Matemáticas aplicadas discretas 159, págs. 683–694
Enlaces adicionales
- Maydanskiy, M. (2005), "La conjetura de coloración de incidencia para gráficos de grado máximo 3" , Matemáticas discretas , 292 , págs. 131-141.
- Hartke, SG; Helleloid, GT (2012), "Reconstrucción de un gráfico a partir de su gráfico de incidencia de arco", Graphs and Combinatorics , 28 , págs. 637–652, doi : 10.1007 / s00373-011-1073-7 , S2CID 14656326.
- Sun, PK; Shiu, WC (2012), "Pruebas no válidas sobre coloración de incidencia" (PDF) , Matemáticas discretas , 54 , págs. 107-114.
- Li, D; Liu, M. (2008), "Coloración de incidencia de los cuadrados de algunas gráficas" , Matemáticas discretas , 308 , págs. 6575–6580.
- Bonamy, M .; Hocquard, H .; Kerdjoudj, S .; Raspaud, A. (2015), Coloración de incidencia de gráficos con grado medio máximo alto , arXiv : 1412.6803 , Bibcode : 2014arXiv1412.6803B.
- Hosseini Dolama, M .; Sopena, E. (2005), "Sobre el grado medio máximo y el número cromático de incidencia de un gráfico" (PDF) , Matemáticas discretas y Ciencias de la Computación Teórica , 7 , pp. 203-216.
- Shiu, WC; Sun, PK (2006), "Gráficos que no son (∆ + 1) -incidencia coloreables con errata del número cromático de incidencia de gráficos planos externos" Verificar
|url=
valor ( ayuda ) (PDF). [ enlace muerto ] - Shiu, WC; Lam, PCP; Chen, DL (2002), "Sobre la coloración de incidencia para algunas gráficas cúbicas" , Matemáticas discretas , 252 , págs. 259-266, doi : 10.1016 / S0012-365X (01) 00457-5.
- Nakprasit, K. (2014), "El fuerte índice cromático de gráficos y subdivisiones" , Matemáticas discretas , 317 , págs. 75–78.
- Ding, KF; Pai, K. J; Chang, JM; Tsaur, R. (2015), "Algunos resultados de coloración de incidencia de gráficos de Petersen generalizados", Sistemas y aplicaciones inteligentes: Actas del Simposio Internacional de Computación (ICS) celebrado en Taichung, Taiwán, 12 a 14 de diciembre de 2014 , 274 , doi : 10.3233 / 978-1-61499-484-8-85.
- Liang, L .; Gao, W. (2010), "Sobre el número cromático de incidencia fraccional del theta-gráfico generalizado" , Journal of Chongqing Normal University , 27 , págs. 36-39.
- Shiu, WC; Lam, PCB; Chen, DL (2002), "Nota sobre la coloración de incidencia para algunas gráficas cúbicas" , Matemáticas discretas , 252 , págs. 259–266.
- Sun, PK; Shiu, WC (2012), "Algunos resultados sobre coloración de incidencia, arboricidad de estrellas y número de dominación" (PDF) , Australasian Journal of Combinitorics , 54 , págs. 107-114.
- Wu, J. (2009), "Algunos resultados sobre el número de coloración de incidencia de un gráfico" , Discrete Mathematics , 309 , págs. 3866–3870.
- Li, X .; Tu, J. (2008), "NP-completitud de la colorabilidad de 4 incidencias de gráficos semicúbicos" , Matemáticas discretas , 308 , págs. 1334-1340.
- Pai, KJ; Chang, JM; Wu, RY (2014), "Coloración de incidencia en hipercubos" , Informática teórica , 557 , págs. 59–65.
- Pai, KJ; Chang, JM; Wu, RY (2014), "On the Incidence Coloring Number of Folded hypercubes" , Actas de la 18a Conferencia Internacional de Ingeniería y Ciencias de la Computación (ICSEC 2014), 30 de julio - 1 de agosto, Khon Kaen, Tailandia , págs. 7-11.
- Sopena, É .; Wu, J (2013), "El número cromático de incidencia de rejillas toroidales", Discussiones Mathematicae Graph Theory , 33 (2): 315–327, arXiv : 0907.3801 , doi : 10.7151 / dmgt.1663 , S2CID 1313615.
- Andrés, SD (2009). "Errata de: El número cromático del juego de incidencia". Matemáticas aplicadas discretas . 158 (6): 728. doi : 10.1016 / j.dam.2009.11.017 .
- Charpentier, C .; Sopena, É. (2015), "El número cromático del juego de incidencia de (a, d) - gráficos descomponibles" , Journal of Discrete Algorithms , 31 , págs. 14-25.
- Wu, J .; Zhu, X. (2008), "El número cromático del juego 6 relajado de gráficos planos externos", Matemáticas discretas , 308 (24): 5974–5980, doi : 10.1016 / j.disc.2007.11.015.
- Meng, X .; Guo, J .; Su, B. (2012), "Coloración de incidencia de pseudo gráficos de Halin" , Matemáticas discretas , 312 (22): 3276–3282, doi : 10.1016 / j.disc.2012.07.024.
- Andrés, SD (2009), "Ligereza de los dígrafos en superficies y número cromático del juego dirigido" , Matemáticas discretas , 309 , págs. 3564–3579.
- Li, X .; Tu, J. (2008), "NP-completitud de la colorabilidad de 4 incidencias de gráficos semicúbicos" , Matemáticas discretas , 308 (7): 1334-1340, arXiv : math / 0607071 , doi : 10.1016 / j.disc. 2007.03.076 , S2CID 59464.
- Zhu, X. (1999), "The Game Coloring Number of Planar Graphs", Journal of Combinatorial Theory, Serie B , 75 (2): 245-258, doi : 10.1006 / jctb.1998.1878.
- Liu, X .; Li, Y. (2005), "El número cromático de incidencia de algún gráfico", Revista Internacional de Matemáticas y Ciencias Matemáticas , 1 (5): 803–813, doi : 10.1155 / IJMMS.2005.803.
- Dong, GX; Liu, XF (2014), "Incidence Coloring Number of Some Join Graphs" , Applied Mechanics and Materials , 602–605: 3185–3188, doi : 10.4028 / www.scientific.net / AMM.602-605.3185 , S2CID 122567953.
Ver también
- L (h, k) -coloring
- Coloración armoniosa
- Coloración de estrellas
- Coloración total
- Coloración circular
- Coloración del camino
- Coloración defectuosa
- Radio para colorear
- Coloración acíclica