Coloración de incidencia

Etiquetado especial en la 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 grafo . La coloración de incidencia es un etiquetado de grafos especial donde a cada incidencia de una arista 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 es incidente 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 = u , e ≠ f
• e = f , v ≠ u
• e = { v , u }, f = { u , w } y v ≠ w .

Ejemplos de incidencias adyacentes o vecinas. El * sobre la arista e más cercana 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 coloración de incidencia de un grafo 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 limitaron en términos de Δ( G ). Inicialmente, se descubrió el número cromático de incidencia de árboles, grafos bipartitos completos y grafos completos. También conjeturaron que todos los grafos pueden tener una coloración de incidencia utilizando Δ( 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. encontraron el número cromático de incidencia de trayectorias , abanicos, ciclos , ruedas, grafos tripartitos completos y ruedas con aristas añadidas. Unos años más tarde, Shiu et al. demostraron que esta conjetura es cierta para ciertos grafos cúbicos, como los grafos hamiltonianos cúbicos. Demostró que en el caso de un grafo plano exterior de grado máximo 4, el número cromático de incidencia no es 5. Ahora se han descubierto los límites para el número cromático de incidencia de varias clases de grafos.

Resultados básicos

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

Demostración. Sea v el vértice con grado máximo Δ en G . Sean las aristas que son incidentes con el vértice v . Consideremos Podemos ver que cada par de incidencias Δ + 1, es decir, son vecinas. Por lo tanto, estas incidencias tienen que ser coloreadas usando 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 gráfico 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 propusieron ciertas condiciones necesarias para que el grafo satisfaga ${\displaystyle \chi _{i}(G)=\Delta (G)+1.}$

• ${\displaystyle \chi _{i}(G)\leq 2\Delta (G).}$
• El número cromático de incidencia del grafo 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 de panal 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 de incidencia de mallas cuadradas, mallas de panal 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 de panal es 4.

Gráficas de Halin

Chen, Wang y Pang demostraron que si G es un gráfico de Halin con ∆( G ) > 4, entonces, para los gráficos de Halin con ∆( G ) = 3 o 4, Jing-Zhe Qu demostró que son 5 o 6 respectivamente. Si el número de coloración de incidencia de los gráficos de Halin con bajo grado 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 todos los grafos cúbicos de Halin, excepto los de , tienen una coloración de incidencia con Δ( G ) + 2 colores. Su, Meng y Guo extendieron este resultado a todos los grafos 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.}$

grafos k-degenerados

DL Chen, PCB Lam y WC Shiu habían conjeturado que el número cromático de incidencia de un grafo cúbico G es como máximo ∆( G ) + 2. Probaron esto para ciertos grafos cúbicos como los grafos cúbicos hamiltonianos. Con base en estos resultados, MH Dolama, E. Sopena y X. Zhu (2004) estudiaron las clases de grafos para los cuales está acotado por ∆( G ) + c donde c es alguna constante fija. ^[5] Se dice que un grafo es k -generado 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 los grafos k -degenerados G es como máximo ∆( G ) + 2 k − 1.
• El número cromático de incidencia de K ₄ grafos libres menores G es como máximo ∆( G ) + 2 y forma un límite estricto.
• El número cromático de incidencia de un grafo planar G es como máximo ∆( G ) + 7.

Gráficos extraplanares

Considérese un grafo exterior plano G con vértice de corte 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 grafo exterior-planar G es como máximo ∆( G ) + 2. En el caso de grafos exteriores-planares con ∆( G ) > 3 el número cromático de incidencia es ∆( G ) + 1.

Dado que los grafos exteriores-planares son grafos libres de K ₄ menores, aceptan una coloración de incidencia (Δ + 2, 2). ^{[5] [6]} La solución para el número cromático de incidencia del grafo exterior-planar G que tiene Δ( G ) = 3 y grafo exterior-planar 2-conexo sigue siendo una cuestión abierta.

Anillos cordales

Los anillos cordales son variaciones de las redes en anillo. El uso de anillos cordales en comunicación está muy extendido 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 extra conocido como cuerda, a algún otro nodo de la red. Las redes de bucles distribuidos son anillos cordales de grado 4 que se construyen añadiendo 2 cuerdas extra en cada vértice de una red en anillo.

El anillo cordal en N nodos y longitud de cuerda d , denotado por CR ( N , d ), es un grafo 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 se estudian debido a 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 cordales. ^[8] Se formularon varios algoritmos para encontrar el número cromático de incidencia de los anillos cordales. Los hallazgos principales 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}}}$

Potencias de ciclos

Keaitsuda Nakprasit y Kittikorn Nakprasit estudiaron la coloración de incidencia de potencias de ciclos. Si 2 k + 1 ≥ n entonces supongamos que n > 2 k + 1 y escribimos: ${\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 pueden resumirse 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 dominancia de un grafo

Proposición. ^[10] Sea G un grafo 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 grafo G dividiendo cada arista 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 propia 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 . Por 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 independiente máximo 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 ha sido ampliamente utilizada en la caracterización de grafos r -regulares coloreables por incidencia ( r + 1) . El principal resultado sobre la coloración por incidencia de grafos r -regulares es: Si el grafo G es un grafo r-regular , entonces si y solo si V ( G ) es una unión disjunta de conjuntos dominantes r + 1 . ^[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 solo 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 definamos

${\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 de intervalo, entonces se dice que es mínima. ${\displaystyle A_{c}(v)}$ ${\displaystyle \chi _{ii}.}$ ${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).}$ ${\displaystyle \chi _{ii}}$

El concepto de coloración por incidencia de intervalo fue introducido por A. Malafiejska, R. Janczewski y M. Malafiejski. Demostraron que para grafos bipartitos ^[13] la igualdad se cumple en el caso de grafos bipartitos regulares. Los grafos bipartitos subcúbicos admiten una coloración por incidencia de intervalo utilizando cuatro, cinco o seis colores. También demostraron que la colorabilidad de incidencia 5 se puede decidir en tiempo lineal para grafos bipartitos con ∆( G ) = 4. ${\displaystyle \chi _{ii}(G)\leq \Delta (G)}$

Coloración de incidencia fraccional

La versión fraccionaria de la coloración de incidencia fue introducida por primera vez por Yang en 2007. Una coloración de incidencia k de r -tuplas de un grafo G es la asignación de r colores a cada incidencia del grafo G de un conjunto de k colores de modo que a las incidencias adyacentes se les dan conjuntos disjuntos de colores. ^[14] Por definición, es obvio que la coloración de incidencia k de 1-tuplas también es una coloración de incidencia k .

El número cromático de incidencia fraccionaria del grafo G es el ínfimo de las fracciones de tal manera que G admite una coloración de incidencia k de r -tupla . La coloración de incidencia fraccionaria tiene grandes aplicaciones en varios campos de la informática. Basándose en los resultados de coloración de incidencia de Guiduli, ^[2] Yang ha demostrado que el número cromático de incidencia fraccionaria de cualquier grafo es como máximo Δ( G ) + 20 log Δ( G ) + 84. También ha demostrado la existencia de grafos con número cromático de incidencia fraccionaria como mínimo Δ( G ) + Ω(log Δ( G )). ${\displaystyle {\tfrac {k}{r}}}$

Desigualdad de Nordhaus-Gaddum

Sea G un grafo con n vértices tal que donde denota el complemento de G . Entonces ^[10] Estos límites son precisos 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 Incidencia

El juego de coloración de incidencia fue introducido por primera vez por SD Andres. ^[15] Es la versión de incidencia del juego de coloración de vértices, en el que se colorean las incidencias de un gráfico 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 teórico del número cromático de incidencia.

El juego consiste en que dos jugadores, Alice y Bob, construyan un colorante de incidencia adecuado. Las reglas se indican a continuación:

• Alice y Bob colorean las incidencias de un gráfico G con un conjunto k de colores.
• Se turnan para dar el color adecuado a un incidente sin color. Generalmente, empieza Alicia.
• En el caso de una incidencia que no se pueda colorear adecuadamente, entonces Bob gana.
• Si cada incidencia del gráfico está coloreada correctamente, Alicia gana.

El número cromático del juego de incidencia de un grafo G , denotado por , es la menor cantidad de colores necesarios para que Alicia gane en un juego de coloración de incidencia. Unifica las ideas de número cromático de incidencia de un grafo y número cromático del juego en el caso de un grafo no dirigido. Andres descubrió que el límite superior para en el caso de grafos k -degenerados es 2Δ + 4 k − 2. Este límite se mejoró a 2Δ + 3 k − 1 en el caso de grafos 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 descubierto el número cromático exacto del juego de incidencia de caminos grandes y ha dado una prueba correcta de un resultado establecido por Andres sobre el número cromático exacto del juego de incidencia de ruedas grandes. ^[16] ${\displaystyle i_{g}(G)}$ ${\displaystyle i_{g}(G)}$

Referencias

1. Algor I., Alon N. (1989); "La arboricidad estelar de los grafos", Discrete Mathematics 75, págs. 11-22.
2. Guiduli B. (1997); "Sobre la coloración de incidencia y la arboricidad estelar de los grafos", Discrete Mathematics 163, págs. 275-278
3. Huang, CI; Wang, YL; Chung, SS (2004), "Los números de coloración de incidencia de las mallas", Computers and Mathematics with Applications 48, págs. 1643-1649
4. Wang, SD; Cheng, DL; Pang, SC (2002), "El número de coloración de incidencia de los gráficos de Halin y los gráficos planos exteriores", Discrete Mathematics 256, págs. 397-405
5. Hosseini Dolama, M.; Sopena, E.; Zhu, X. (2004), "Coloración de incidencia de gráficos generados por k", Discrete Mathematics 283, págs. 121-128
6. Wang, S.; Xu, J.; Ma, F.; Xu, C. (2008), "La coloración de incidencia (Δ + 2, 2) de gráficos planos exteriores", Progress in Natural Science 18, págs. 575–578.
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 el número de coloración de incidencia de anillos cordales*", 32º Taller sobre Matemática Combinatoria y Teoría de la Computación, págs. 89-93.
9. Nakprasit, Keaitsuda y Nakprasit, Kittikorn (2012), "Coloraciones de incidencia de las potencias de los ciclos", Revista internacional de matemáticas puras y aplicadas 76(1), pp. 143-148
10. Sun, PK (2012), "Coloración de incidencia de gráficos regulares y gráficos complementarios", Revista taiwanesa de matemáticas 16, n.º 6, págs. 2289-2295
11. Janczewski, R.; Malafiejska, A.; Malafiejski, M., "Asignación de longitud de onda de intervalo en redes estelares totalmente ópticas", Procesamiento paralelo y matemáticas aplicadas, 8.ª conferencia internacional, PPAM 2009, Wtroclaw, Polonia, 13-16 de septiembre de 2009. Documentos seleccionados revisados, parte I (Springer), págs. 11-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 de gráficos de incidencia de intervalos", Discrete Applied Mathematics 182, págs. 73-83
13. Janczewski, R.; Małafiejska, A.; Małafiejski, M. (2014), "Coloración de la incidencia de intervalos de gráficos bipartitos", Discrete Applied Mathematics 166, págs. 131-145
14. Yang, D (2012), "Coloración de incidencia fraccional y arboricidad estelar de grafos", Ars Combinatoria - Waterloo then Winnipeg 105, pp. 213–224
15. Andres, SD (2009), "El juego de incidencia del número cromático", Matemáticas Aplicadas Discretas 157, pp. 1980–1987
16. Kim, JY (2011), "El juego de incidencia del número cromático de trayectorias y subgrafos de ruedas", Discrete Applied Mathematics 159, pp. 683–694

Enlaces adicionales

• Maydanskiy, M. (2005), "La conjetura de coloración de incidencia para gráficos de grado máximo 3", Discrete Mathematics , 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", Graphs and Combinatorics , vol. 28, págs. 637–652, doi :10.1007/s00373-011-1073-7, S2CID  14656326.
• Sun, PK; Shiu, WC (2012), "Pruebas inválidas sobre coloración de incidencia" (PDF) , Discrete Mathematics , vol. 54, págs. 107–114.
• Li, D; Liu, M. (2008), "Coloración de incidencia de los cuadrados de algunos gráficos", Discrete Mathematics , vol. 308, págs. 6575–6580.
• Bonamy, M.; Hocquard, H.; Kerdjoudj, S.; Raspaud, A. (2015), Coloración de incidencia de gráficos con un 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 grafo" (PDF) , Discrete Mathematics and Theoretical Computer Science , vol. 7, págs. 203–216.
• Shiu, WC; Lam, PCP; Chen, DL (2002), "Sobre la coloración de incidencia para algunos gráficos cúbicos", Discrete Mathematics, vol. 252, págs. 259–266, doi :10.1016/S0012-365X(01)00457-5.
• Nakprasit, K. (2014), "El índice cromático fuerte de gráficos y subdivisiones", Discrete Mathematics , vol. 317, págs. 75–78.
• Ding, KF; Pai, K. J; Chang, JM; Tsaur, R. (2015), "Algunos resultados de la coloración de incidencia de gráficos Petersen generalizados", Sistemas inteligentes y aplicaciones: Actas del Simposio internacional de informática (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 fraccionaria de grafos theta generalizados", Journal of Chongqing Normal University , vol. 27, págs. 36–39.
• Shiu, WC; Lam, PCB; Chen, DL (2002), "Nota sobre la coloración de incidencia para algunos gráficos cúbicos", Discrete Mathematics , vol. 252, págs. 259–266.
• Sun, PK; Shiu, WC (2012), "Algunos resultados sobre la coloración de 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 el número de coloración de incidencia de un gráfico", Discrete Mathematics , vol. 309, págs. 3866–3870.
• Li, X.; Tu, J. (2008), "NP-completitud de la colorabilidad de 4 incidencias de gráficos semicúbicos", Discrete Mathematics , vol. 308, págs. 1334–1340.
• Pai, KJ; Chang, JM; Wu, RY (2014), "Coloración de incidencia en hipercubos", Theoretical Computer Science , vol. 557, págs. 59–65.
• Pai, KJ; Chang, JM; Wu, RY (2014), "Sobre el número de coloración de incidencia de hipercubos plegados", 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.
• Sopena, É.; Wu, J (2013), "El número cromático de incidencia de las cuadrículas toroidales", Discussiones Mathematicae Graph Theory , 33 (2): 315–327, arXiv : 0907.3801 , doi :10.7151/dmgt.1663, S2CID  1313615.
• Andres, SD (2009). "Fe de erratas de: El juego de incidencia del número cromático". Matemáticas Aplicadas Discretas . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
• Charpentier, C.; Sopena, É. (2015), "El juego de incidencia del número cromático de grafos descomponibles (a,d)", Journal of Discrete Algorithms , vol. 31, págs. 14–25.
• Wu, J.; Zhu, X. (2008), "El número cromático del juego relajado 6 de grafos planos exteriores", Discrete Mathematics , 308 (24): 5974–5980, doi : 10.1016/j.disc.2007.11.015.
• Meng, X.; Guo, J.; Su, B. (2012), "Coloración de incidencia de pseudografos de Halin", Discrete Mathematics , 312 (22): 3276–3282, doi :10.1016/j.disc.2012.07.024.
• Andres, SD (2009), "Ligereza de dígrafos en superficies y juego dirigido de números cromáticos", Matemáticas Discretas , vol. 309, pp. 3564–3579.
• Li, X.; Tu, J. (2008), "NP-completitud de la colorabilidad de 4 incidencias de gráficos semicúbicos", Discrete Mathematics , 308 (7): 1334–1340, arXiv : math/0607071 , doi :10.1016/j.disc.2007.03.076, S2CID  59464.
• Zhu, X. (1999), "El juego de colorear números de grafos planares", 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 grafo", 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", Applied Mechanics and Materials , 602–605: 3185–3188, doi :10.4028/www.scientific.net/AMM.602-605.3185, S2CID  122567953.

Véase también

• Coloración L(h, k)
• Coloración armoniosa
• Colorear estrellas
• Coloración total
• Coloración circular
• Colorear caminos
• Coloración defectuosa
• Colorear la radio
• Coloración acíclica