Coloración de incidencia

Etiquetado especial en teoría de grafos.

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

A continuación, G denota un gráfico simple con un conjunto de vértices no vacíos (no vacío) V ( G ), un conjunto de aristas 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 incide en la arista e . Se dice que dos incidencias ( v , e ) y ( u , f ) son adyacentes o vecinas si se cumple una de las siguientes condiciones: ${\displaystyle v\in V(G)}$ ${\displaystyle e\in E(G).}$

• v = tu , mi ≠ f
• mi = f , v ≠ tu
• mi = { v , u }, f = { u , w } y v ≠ w .

Ejemplos de incidencias adyacentes/vecinas. El * sobre el borde e más cercano al vértice v denota incidencia (v,e).

Definición. Sea I ( 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 ) en lugar de c (( v , e )).) El número mínimo de colores necesarios para la incidencia La coloración de un gráfico G se conoce como número cromático de incidencia o número de coloración de incidencia de G , representado por Esta notación fue introducida por Jennifer J. Quinn Massey y Richard A. Brualdi en 1993. ${\displaystyle c:I(G)\to \mathbb {N} }$ ${\displaystyle \chi _{i}(G).}$

Coloración de incidencia de un gráfico de Petersen

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 determinó la incidencia del número cromático de árboles, gráficas bipartitas completas y gráficas completas. 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 de incidencia es un caso de arboricidad estelar 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 et al. Se encontró la incidencia cromática del número de caminos , abanicos, ciclos , ruedas, grafo tripartito completo y sumando ruedas de arista. Unos años más tarde, Shiu et al. demostró que esta conjetura es cierta para ciertos gráficos cúbicos , como los gráficos hamiltonianos cúbicos. Demostró que en el caso de un gráfico plano externo de grado máximo 4, el número cromático de incidencia no es 5. Ahora se descubren los límites para el número cromático de incidencia de varias clases de gráficos.

Resultados básicos

Proposición. ${\displaystyle \chi _{i}(G)\geq \Delta (G)+1.}$

Prueba. Sea v el vértice de máximo grado Δ en G . Sean las aristas que inciden con el vértice v . Consideremos que podemos ver que cada par de incidencias Δ + 1, es decir, es vecina. Por tanto, estas incidencias hay que colorearlas con colores distintos. ${\displaystyle e_{1},e_{2},\ldots ,e_{\Delta }}$ ${\displaystyle e_{1}=\{v,w\}.}$ ${\displaystyle (v,e_{1}),(v,e_{2}),\ldots ,(v,e_{\Delta }),(w,e_{1})}$

El límite se alcanza mediante árboles y gráficos completos:

• Si G es un grafo completo con al menos dos vértices, entonces ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$
• Si G es un árbol con al menos dos vértices, entonces ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

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 ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• El número cromático de incidencia del gráfico bipartito completo con m ≥ n ≥ 2, es m + 2. ${\displaystyle K_{m,n}}$
• ${\displaystyle \chi _{i}(C_{n})\leq 4}$y ${\displaystyle \chi _{i}(C_{3n})=3.}$

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 realizar en el tiempo lineal con la menor cantidad de colores. Se descubre que se requieren ∆( G ) + 1 colores para la coloración por 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 entonces, para gráficos de Halin con ∆( G ) = 3 o 4, Jing-Zhe Qu demostró 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 sigue siendo un problema sin resolver. ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$ ${\displaystyle \chi _{i}(G)}$

Shiu y Sun demostraron que cada gráfico cúbico de Halin que no sea tiene una coloración de incidencia con Δ ( G ) + 2 colores. Su, Meng y Guo ampliaron este resultado a todos los gráficos pseudo-Halin. ${\displaystyle K_{4}}$

Si el gráfico de Halin G contiene un árbol T , entonces ^[4] ${\displaystyle \chi _{i}(G^{2})\leq \Delta (T^{2})+\Delta (T)+8.}$

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 gráficos para las cuales está acotado por ∆( G ) + c donde c es una constante fija. ^[5] Se dice que un gráfico está generado por k si para cada subgrafo H de G , el grado mínimo de H es como máximo k . ${\displaystyle \chi _{i}(G)}$

• El número cromático de incidencia de k -gráficos degenerados G es como máximo ∆( G ) + 2 k − 1.
• El número cromático de incidencia de K ₄ 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 exteriores

Considere un gráfico plano externo G con vértice cortado v tal que G – v es la unión de y . Sea (resp. ) el subgrafo inducido en el vértice v y los vértices de (resp. ). Entonces es el máximo de y donde es el grado del vértice v en G. ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle \chi _{i}(G)}$ ${\displaystyle \chi _{i}(G_{1}),\chi _{i}(G_{2})}$ ${\displaystyle 1+d_{G}(v)}$ ${\displaystyle d_{G}(v)}$

El número cromático de incidencia de un gráfico plano externo G es como máximo ∆( G ) + 2. En el caso de gráficos planos externos con ∆( G ) > 3, el número cromático de incidencia es ∆( G ) + 1.

Dado que los gráficos planos externos son K ₄ -gráficos libres de 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 plano exterior G que tiene Δ( G ) = 3 y un gráfico 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 comunicación es muy extendido debido a sus ventajas sobre las redes de interconexión con topología en anillo y otras estructuras analizadas como mallas, hipercubos, gráficas 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 cuerda, con algún otro nodo de la red. Las redes de bucle distribuido 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 cordal en N nodos y longitud de cuerda d , denotado por CR ( N , d ), es un gráfico definido como:

${\displaystyle {\begin{aligned}V(G)&=\{v_{0},v_{1},\ldots ,v_{N-1}\}\\E(G)&=\{v_{i}v_{j}:i-j\equiv 1,d{\bmod {N}}\}\end{aligned}}}$

Estos gráficos son estudiados por su aplicación en la comunicación. Kung-Fu Ding, Kung-Jui Pai y Ro-Yu Wu estudiaron la coloración de incidencia de los anillos de cuerdas. ^[8] Se formulan varios algoritmos para encontrar el número cromático de incidencia de anillos cordales. Los principales hallazgos son:

${\displaystyle {\begin{aligned}\chi _{i}(CR(N,2))&={\begin{cases}5&5|N\\6&{\text{otherwise}}\end{cases}}\\\chi _{i}(CR(N,3))&={\begin{cases}5&5|N\\6&N\equiv 2{\bmod {5}}\end{cases}}\end{aligned}}}$

poderes de ciclos

Keaitsuda Nakprasit y Kittikorn Nakprasit estudiaron la coloración de incidencia de las potencias de los ciclos. Si 2 k + 1 ≥ n , entonces supongamos n > 2 k + 1 y escriba: ${\displaystyle C_{n}^{k}.}$ ${\displaystyle C_{n}^{k}=K_{n}}$

${\displaystyle n=(2k+1)t+r,\quad 1\leq t,\quad 0\leq r\leq 2k.}$

Sus resultados se pueden resumir de la siguiente manera: ^[9]

${\displaystyle {\begin{aligned}\chi _{i}(C_{n}^{k})&={\begin{cases}2k+1&r=0\\2k+2&1\leq r\leq t{\text{ or }}r=2k\end{cases}}&&k\geq 3\\\chi _{i}(C_{n}^{2})&={\begin{cases}5&5|n\\6&{\text{otherwise}}\end{cases}}\end{aligned}}}$

La relación con la conjetura de coloración de incidencia viene dada por la observación de que ${\displaystyle \Delta (C_{n}^{k})=2k.}$

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 un gráfico conexo simple de orden n , tamaño m y número de dominación . Entonces ${\displaystyle \gamma .}$ ${\displaystyle \chi _{i}(G)\geq {\tfrac {2m}{n-\gamma }}.}$

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 de 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 tanto, un conjunto máximo independiente de arcos es un bosque de estrellas máximo . Esto implica que se requieren al menos clases de color. ^[10] ${\displaystyle {\overrightarrow {uv}}}$ ${\displaystyle {\overrightarrow {xy}}}$ ${\displaystyle {\tfrac {2m}{n-\gamma }}}$

Esta relación se ha utilizado ampliamente en la caracterización de gráficos regulares r coloreables de incidencia ( r + 1) . El principal resultado sobre la coloración de incidencia de gráficos r -regulares es: Si el gráfico G es un gráfico r-regular , entonces si y solo si V ( G ) es una unión disjunta de r + 1 conjuntos dominantes . ^[10] ${\displaystyle \chi _{i}(G)=\chi _{i}(G^{2})=r+1}$

Coloración de incidencia de intervalo

Definición. Un subconjunto finito es un intervalo si y sólo si contiene todos los números entre su mínimo y su máximo. ${\displaystyle A\subset \mathbb {N} }$

Definición. Sea c una coloración de incidencia de G y defina

${\displaystyle A_{c}(v)=\{c(v,e):(v,e)\in I(G)\}.}$

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 conjunto es un intervalo. ^{[11] [12]} El número de coloración de incidencia de intervalo de G es el número mínimo de colores utilizados para la coloración de incidencia de intervalo de G . Se denota por Está claro que si solo se utilizan colores para la coloración de incidencia del intervalo, entonces se dice que es mínimo. ${\displaystyle A_{c}(v)}$ ${\displaystyle \chi _{ii}.}$ ${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).}$ ${\displaystyle \chi _{ii}}$

El concepto de coloración de incidencia de intervalo fue introducido por A. Malafiejska, R. Janczewski y M. Malafiejski. Probaron para 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 5-colorabilidad se puede decidir en tiempo lineal para gráficos bipartitos con ∆ ( G ) = 4. ${\displaystyle \chi _{ii}(G)\leq \Delta (G)}$

Coloración de incidencia fraccionada

La versión fraccionada de la coloración de incidencia fue introducida por primera vez por Yang en 2007. Una k -coloración de incidencia r -tuple de un gráfico G es la asignación de r colores a cada incidencia del gráfico G de un conjunto de k colores tales que las incidencias adyacentes reciben conjuntos de colores disjuntos. ^[14] Por definición, es obvio que la incidencia de 1 tupla k -coloración es una incidencia k -coloración también.

El número cromático de incidencia fraccionaria del gráfico G es el mínimo de las fracciones de tal forma que G admite una incidencia r -tupla 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 coloración fraccionaria. número cromático de incidencia al menos Δ( G ) + Ω(log Δ( G )). ${\displaystyle {\tfrac {k}{r}}}$

Desigualdad de Nordhaus-Gaddum

Sea G un gráfico con n vértices tal que donde denota el complemento de G. Entonces ^[10] Estos límites son nítidos para todos los valores de n . ${\displaystyle G\neq K_{n},{\overline {K_{n}}}}$ ${\displaystyle {\overline {G}}}$ ${\displaystyle n+2\leq \chi _{i}(G)+\chi _{i}({\overline {G}})\leq 2n-1.}$

Juego de colorear de incidencia

El juego de colorear de incidencia fue introducido por primera vez por SD Andrés. ^[15] Es la versión de incidencia del juego de colorear vértices, en el que se colorean las incidencias de un gráfico en lugar de los vértices. El número cromático de incidencia del juego es el nuevo parámetro definido como un análogo en teoría de juegos 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 un gráfico G con un conjunto k de colores.
• Se turnan para proporcionar una coloración adecuada a una incidencia sin color. 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 el caso de un gráfico no dirigido. Andrés descubrió que el límite superior en el caso de k -gráficos 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 la incidencia del número cromático de estrellas, ciclos y ruedas suficientemente grandes. ^[15] John Y. Kim (2011) ha descubierto el número cromático exacto del juego de incidencia de ruedas grandes y ha dado una prueba correcta de un resultado declarado por Andrés sobre el número cromático exacto del juego de incidencia de ruedas grandes. ^[dieciséis] ${\displaystyle i_{g}(G)}$ ${\displaystyle i_{g}(G)}$

Referencias

1. Algor I., Alon N. (1989); "La arboricidad estelar de las gráficas", Matemáticas Discretas 75, págs. 11-22.
2. Guiduli B. (1997); "Sobre la coloración de incidencia y la arboricidad de las estrellas en los gráficos", Matemáticas Discretas 163, págs. 275-278
3. Huang, CI; Wang, YL; Chung, SS (2004), "The Incidence Coloring Numbers of Meshes", Computadoras y matemáticas con aplicaciones 48, págs. 1643-1649
4. Wang, SD; Cheng, DL; Pang, SC (2002), "El número de coloración de incidencia de gráficos de Halin y gráficos planos externos", Matemáticas discretas 256, págs. 397–405
5. Hosseini Dolama, M.; Sopeña, E.; Zhu, X. (2004), "Coloración de incidencia de gráficos generados por k", Matemáticas discretas 283, págs. 121-128
6. Wang, S.; Xu, J.; Mamá, F.; Xu, C. (2008), "La coloración de incidencia (Δ + 2, 2) de gráficos planos externos", Progress in Natural Science 18, págs.
7. Arden BW, Lee H. (1981); "Análisis de la red de anillos cordales", IEEE Transactions on Computers 30, págs. 291-295.
8. Ding KF, Pai KJ, Yu R. (1981); "Algunos resultados sobre la incidencia de coloración del número de anillos cordales *", 32º taller sobre matemáticas combinatorias y teoría de la computación, págs.
9. Nakprasit, Keaitsuda y Nakprasit, Kittikorn (2012), "Colorantes de incidencia de las potencias de los ciclos", Revista internacional de matemáticas puras y aplicadas 76 (1), págs.
10. Sun, PK (2012), "Coloración de incidencia de gráficos regulares y gráficos de complemento", Taiwanese Journal of Mathematics 16, No. 6, págs.
11. 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 al 16 de septiembre de 2009. Artículos seleccionados revisados, Parte I (Springer), págs. 11 a 20, doi:10.1007/978-3-642-14390-8_2, ISBN  978-3-642-14389-2
12. Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2015), "Coloración del gráfico de incidencia de intervalos", Matemáticas aplicadas discretas 182, págs.
13. Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2014), "Coloración de incidencia de intervalos de gráficos bipartitos", Matemáticas aplicadas discretas 166, págs.
14. Yang, D (2012), "Coloración de incidencia fraccionada y arboricidad estelar de gráficos", Ars Combinatoria - Waterloo y luego Winnipeg 105, págs.
15. Andres, SD (2009), "El número cromático del juego de incidencia", Matemáticas Aplicadas Discretas 157, págs. 1980-1987
16. Kim, JY (2011), "El número cromático de trayectorias y subgrafos de ruedas del juego de incidencia", Matemáticas Aplicadas Discretas 159, págs.

Enlaces adicionales

• Maydanskiy, M. (2005), "La conjetura de coloración de incidencia para gráficas de grado máximo 3", Matemáticas Discretas , vol. 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", Gráficos y combinatoria , vol. 28, págs. 637–652, doi :10.1007/s00373-011-1073-7, S2CID  14656326.
• Sol, PK; Shiu, WC (2012), "Pruebas no válidas sobre coloración de incidencia" (PDF) , Matemáticas discretas , vol. 54, págs. 107-114.
• Li, D; Liu, M. (2008), "Coloración de incidencia de los cuadrados de algunas gráficas", Matemáticas Discretas , vol. 308, págs. 6575–6580.
• Bonami, M.; Hocquard, H.; Kerdjoudj, S.; Raspaud, A. (2015), Coloración de incidencia de gráficos con grado promedio 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ática Discreta e Informática Teórica , vol. 7, págs. 203-216.
• Shiu, WC; Lam, PCP; Chen, DL (2002), "Sobre la coloración de incidencia de algunas gráficas cúbicas", Matemáticas discretas, vol. 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 , vol. 317, págs. 75–78.
• Ding, KF; Pai, KJ; Chang, JM; Tsaur, R. (2015), "Algunos resultados de la 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, del 12 al 14 de diciembre de 2014 , vol. 274, IOS Press, págs. 85–91, 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-graph generalizado", Revista de la Universidad Normal de Chongqing , vol. 27, págs. 36-39.
• Shiu, WC; Lam, PCB; Chen, DL (2002), "Nota sobre la coloración de incidencia de algunas gráficas cúbicas", Matemáticas discretas , vol. 252, págs. 259-266.
• Sol, PK; Shiu, WC (2012), "Algunos resultados sobre la coloración de la incidencia, la arboricidad de las estrellas y el número de dominación" (PDF) , Australasian Journal of Combinitorics , vol. 54, págs. 107-114.
• Wu, J. (2009), "Algunos resultados sobre la incidencia del número de coloración de un gráfico", Matemáticas Discretas , vol. 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 , vol. 308, págs. 1334-1340.
• Pai, KJ; Chang, JM; Wu, RY (2014), "Coloración de incidencia en hipercubos", Informática teórica , vol. 557, págs. 59–65.
• Pai, KJ; Chang, JM; Wu, RY (2014), "On the Incidence Coloring Number of Folded hypercubes", Actas de la 18.ª 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.
• Sopeña, É.; 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 a: El número cromático del juego de incidencia". Matemática Aplicada Discreta . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Charpentier, C.; Sopeña, É. (2015), "El número cromático del juego de incidencia de (a,d) - gráficos descomponibles", Journal of Discrete Algorithms , vol. 31, págs. 14-25.
• Wu, J.; Zhu, X. (2008), "El número cromático de gráficos externos del juego relajado de 6", 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 pseudográficos de Halin", Matemáticas discretas , 312 (22): 3276–3282, doi :10.1016/j.disc.2012.07.024.
• Andrés, SD (2009), “Ligereza de dígrafos en superficies y juego cromático dirigido del número”, Matemática Discreta , vol. 309, págs. 3564–3579.
• Li, X.; Tu, J. (2008), "Completitud NP 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), "Número de coloración de incidencia de algunos gráficos de unión", Materiales y mecánica aplicada , 602–605: 3185–3188, doi :10.4028/www.scientific.net/AMM.602-605.3185, S2CID  122567953.

Ver también

• Coloración L(h, k)
• Coloración armoniosa
• Coloración de estrellas
• coloración total
• Coloración circular
• Coloración del camino
• Coloración defectuosa
• coloración de radio
• Coloración acíclica