En el estudio de problemas de coloración de grafos en matemáticas y ciencias de la computación , una coloración codiciosa o coloración secuencial [1] es una coloración de los vértices de una gráfica formada por un algoritmo codicioso que considera los vértices de la gráfica en secuencia y asigna a cada vértice su primer color disponible . Los colorantes codiciosos se pueden encontrar en tiempo lineal, pero en general no utilizan la cantidad mínima de colores posible.
Las diferentes elecciones de la secuencia de vértices producirán típicamente diferentes colores del gráfico dado, por lo que gran parte del estudio de los colores codiciosos se ha centrado en cómo encontrar un buen orden. Siempre existe una ordenación que produce una coloración óptima, pero aunque tales ordenaciones se pueden encontrar para muchas clases especiales de gráficos, en general son difíciles de encontrar. Las estrategias comúnmente utilizadas para el ordenamiento de vértices implican colocar vértices de mayor grado antes que vértices de menor grado, o elegir vértices con menos colores disponibles en lugar de vértices que están menos restringidos.
Las variaciones de colores codiciosos eligen los colores de forma online , sin ningún conocimiento de la estructura de la parte sin colorear del gráfico, o eligen otros colores distintos al primero disponible para reducir el número total de colores. Se han aplicado algoritmos codiciosos de coloración para programar y problemas de asignación de registros , el análisis de juegos combinatorios y las demostraciones de otros resultados matemáticos, incluido el teorema de Brooks sobre la relación entre coloración y grado. Otros conceptos en la teoría de grafos derivados de coloraciones codiciosas incluyen el número de Grundy de una gráfica (la mayor cantidad de colores que se pueden encontrar mediante una coloración codiciosa) y las gráficas bien coloreadas , gráficas para las cuales todas las coloraciones codiciosas usan el mismo número de colores. colores.
Algoritmo
La coloración codiciosa para un orden de vértice dado se puede calcular mediante un algoritmo que se ejecuta en tiempo lineal . El algoritmo procesa los vértices en el orden dado, asignando un color a cada uno a medida que se procesa. Los colores pueden estar representados por números.y a cada vértice se le asigna el color con el número más pequeño que no haya sido utilizado por uno de sus vecinos. Para encontrar el color más pequeño disponible, se puede usar una matriz para contar el número de vecinos de cada color (o alternativamente, para representar el conjunto de colores de los vecinos) y luego escanear la matriz para encontrar el índice de su primer cero. [2]
En Python , el algoritmo se puede expresar como:
def first_available ( color_list ): "" "Devuelve el entero no negativo más pequeño que no está en la lista de colores dada." "" color_set = set ( color_list ) count = 0 while True : si el recuento no está en color_set : devuelve count count + = 1 def greedy_color ( G , order ): "" "Encuentra el color codicioso de G en el orden dado. Se supone que la representación de G es como https://www.python.org/doc/essays/graphs/ al permitir vecinos de un nodo / vértice para ser iterado por "para w en G [nodo]". El valor de retorno es un diccionario que asigna vértices a sus colores. "" " color = dict () para el nodo en orden : used_neighbour_colors = [ color [ nbr ] para nbr en G [ nodo ] si nbr en color ] color [ nodo ] = first_available ( used_neighbour_colors ) return color
La first_available
subrutina toma un tiempo proporcional a la longitud de su lista de argumentos, porque realiza dos ciclos, uno sobre la propia lista y otro sobre una lista de recuentos que tiene la misma longitud. El tiempo para el algoritmo de coloración general está dominado por las llamadas a esta subrutina. Cada borde del gráfico contribuye a solo una de estas llamadas, la del punto final del borde que se encuentra más adelante en la ordenación de vértices. Por lo tanto, la suma de las longitudes de las listas de argumentos first_available
y el tiempo total del algoritmo son proporcionales al número de aristas del gráfico. [2]
Un algoritmo alternativo, que produce el mismo color, [3] es elegir los conjuntos de vértices con cada color, un color a la vez. En este método, cada clase de colorse elige escaneando los vértices en el orden dado. Cuando este escaneo encuentra un vértice sin color que no tiene vecino en , agrega a . De este modo,se convierte en un conjunto independiente máximo entre los vértices a los que aún no se les asignaron colores más pequeños. El algoritmo encuentra repetidamente clases de color de esta manera hasta que todos los vértices están coloreados. Sin embargo, implica realizar varios escaneos del gráfico, un escaneo para cada clase de color, en lugar del método descrito anteriormente, que utiliza un solo escaneo. [4]
Elección de pedido
Los diferentes ordenamientos de los vértices de un gráfico pueden hacer que los colores codiciosos usen diferentes números de colores, que van desde el número óptimo de colores hasta, en algunos casos, un número de colores que es proporcional al número de vértices en el gráfico. Por ejemplo, un gráfico de corona (un gráfico formado a partir de dos conjuntos disjuntos de n / 2 vértices { a 1 , a 2 , ... } y { b 1 , b 2 , ... } conectando a i con b j siempre que i ≠ j ) puede ser un caso particularmente malo para colorear codiciosos. Con el vértice ordenando a 1 , b 1 , a 2 , b 2 , ... , un colorante codicioso usará n / 2 colores, un color para cada par ( a i , b i ) . Sin embargo, el número óptimo de colores para este gráfico es dos, un color para los vértices a i y otro para los vértices b i . [5] También existen gráficos tales que, con alta probabilidad, un orden de vértices elegido al azar conduce a un número de colores mucho mayor que el mínimo. [6] Por lo tanto, es de cierta importancia en los colores codiciosos elegir cuidadosamente el orden de los vértices.
Buenos pedidos
Los vértices de cualquier gráfico siempre se pueden ordenar de tal manera que el algoritmo codicioso produzca una coloración óptima. Porque, dado cualquier color óptimo, se pueden ordenar los vértices por sus colores. Luego, cuando se usa un algoritmo codicioso con este orden, el color resultante es automáticamente óptimo. [7] Sin embargo, debido a que el color óptimo de los gráficos es NP-completo , cualquier subproblema que permita resolver este problema rápidamente, incluida la búsqueda de un orden óptimo para colores codiciosos, es NP-difícil . [8]
En las gráficas de intervalo y las gráficas cordales , si los vértices están ordenados al revés de un orden de eliminación perfecto , entonces los vecinos anteriores de cada vértice formarán una camarilla . Esta propiedad hace que la coloración codiciosa produzca una coloración óptima, porque nunca usa más colores de los requeridos para cada una de estas camarillas. Un orden de eliminación se puede encontrar en tiempo lineal, cuando existe. [9]
Más claramente, cualquier orden de eliminación perfecto es hereditariamente óptimo , lo que significa que es óptimo tanto para el gráfico en sí como para todos sus subgrafos inducidos . Los gráficos perfectamente ordenables (que incluyen gráficos de cuerdas , gráficos de comparabilidad , y gráficos de distancia-hereditaria ) se definen como los gráficos que tienen un ordenamiento hereditariamente óptima. [10] Reconocer gráficos perfectamente ordenables también es NP-completo. [11]
Malos pedidos
El número de colores producidos por la coloración codiciosa para el peor orden de un gráfico dado se denomina número de Grundy . [12] Así como es difícil encontrar un buen orden de vértices para colorear codiciosos, también lo es encontrar un orden de vértices incorrecto. Es NP-completo determinar, para un gráfico G y un número k dados , si existe un orden de los vértices de G que hace que el algoritmo codicioso use k o más colores. En particular, esto significa que es difícil encontrar el peor de pedidos para G . [12]
Gráficos cuyo orden es irrelevante
Los gráficos bien coloreados son los gráficos para los que todos los colores de vértice producen el mismo número de colores. Este número de colores, en estos gráficos, es igual al número cromático y al número de Grundy. [12] Incluyen las cografías , que son exactamente las gráficas en las que todas las subgrafias inducidas están bien coloreadas. [13] Sin embargo, es co-NP-completo determinar si un gráfico está bien coloreado. [12]
Si se dibuja un gráfico aleatorio del modelo Erdős-Rényi con probabilidad constante de incluir cada borde, entonces cualquier orden de vértice que se elija independientemente de los bordes del gráfico conduce a una coloración cuyo número de colores es cercano al doble del valor óptimo, con alto probabilidad . Se desconoce si existe algún método de tiempo polinomial para encontrar colores significativamente mejores de estos gráficos. [3]
Degeneración
Debido a que los ordenamientos óptimos de los vértices son difíciles de encontrar, se han utilizado heurísticas que intentan reducir el número de colores sin garantizar un número óptimo de colores. Un orden de uso común para colorear codicioso es elegir un vértice v de grado mínimo , ordenar el subgrafo con v eliminado de forma recursiva y luego colocar v último en el orden. El mayor grado de vértice eliminado que encuentra este algoritmo se llama degeneración del gráfico, denotado d . En el contexto de la coloración codiciosa, la misma estrategia de ordenación también se denomina última ordenación más pequeña. [14] Este orden de vértices y la degeneración pueden calcularse en tiempo lineal. [15] Puede verse como una versión mejorada de un método de ordenación de vértices anterior, el orden más grande primero, que ordena los vértices en orden descendente por grados. [dieciséis]
Con el orden de degeneración, la coloración codiciosa utilizará como máximo d + 1 colores. Esto se debe a que, cuando se colorea, cada vértice tendrá como máximo d vecinos ya coloreados, por lo que uno de los primeros d + 1 colores estará libre para su uso. [17] La coloración codiciosa con el orden de degeneración puede encontrar coloraciones óptimas para ciertas clases de gráficos, incluidos árboles, pseudoforestales y gráficos de copas. [18] Markossian, Gasparian y Reed (1996) definen un gráfico ser - estar -perfecto si, para y cada subgrafo inducido de, el número cromático es igual a la degeneración más uno. Para estos gráficos, el algoritmo codicioso con el orden de degeneración es siempre óptimo. [19] Cada-El gráfico perfecto debe ser un gráfico sin agujeros pares , porque los ciclos pares tienen el número cromático dos y la degeneración dos, no coinciden con la igualdad en la definición de-Gráficos perfectos. Si un gráfico y su gráfico de complemento son ambos libres de agujeros pares, ambos son-Perfecto. Las gráficas que son gráficas perfectas y-Las gráficas perfectas son exactamente las gráficas cordales . En gráficos uniformes sin agujeros de manera más general, el orden de degeneración se aproxima a la coloración óptima dentro de, como máximo, el doble del número óptimo de colores; es decir, su razón de aproximación es 2. [20] En los gráficos de disco unitario, su razón de aproximación es 3. [21] El prisma triangular es el gráfico más pequeño para el cual uno de sus ordenamientos de degeneración conduce a una coloración no óptima, y el cuadrado el antiprisma es el gráfico más pequeño que no se puede colorear de manera óptima utilizando ninguno de sus ordenamientos de degeneración. [18]
Órdenes adaptables
Brélaz (1979) propone una estrategia, denominada DSatur , para el ordenamiento de vértices en coloración codiciosa que entrelaza la construcción del ordenamiento con el proceso de coloración. En su versión del algoritmo de coloración codicioso, el siguiente vértice para colorear en cada paso se elige como el que tiene el mayor número de colores distintos en su vecindad . En caso de empates, se elige un vértice de grado máximo en el subgrafo de vértices incoloros entre los vértices empatados. Al realizar un seguimiento de los conjuntos de colores vecinos y sus cardinalidades en cada paso, es posible implementar este método en tiempo lineal. [22]
Este método puede encontrar los colores óptimos para gráficos bipartitos , [23] todos los gráficos de cactus , todos los gráficos de rueda , todos los gráficos en un máximo de seis vértices y casi todos los -Gráfica coloreable. [24] Aunque Lévêque & Maffray (2005) originalmente afirmaron que este método encuentra colores óptimos para los gráficos de Meyniel , más tarde encontraron un contraejemplo a esta afirmación. [25]
Esquemas de selección de color alternativos
Es posible definir variaciones del codicioso algoritmo de coloración en el que los vértices del gráfico dado se colorean en una secuencia determinada, pero en el que el color elegido para cada vértice no es necesariamente el primer color disponible. Estos incluyen métodos en los que el algoritmo desconoce la parte no coloreada del gráfico, o en los que el algoritmo tiene cierta libertad para tomar mejores decisiones de color que el algoritmo básico codicioso.
Selección online
Se han estudiado estrategias alternativas de selección de color en el marco de algoritmos en línea . En el problema de coloración de gráficos en línea, los vértices de un gráfico se presentan uno a la vez en un orden arbitrario a un algoritmo de coloración; el algoritmo debe elegir un color para cada vértice, basándose únicamente en los colores y las adyacencias entre los vértices ya procesados. En este contexto, se mide la calidad de una estrategia de selección de color por su relación competitiva , la relación entre el número de colores que utiliza y el número óptimo de colores para el gráfico dado. [26]
Si no se dan restricciones adicionales en el gráfico, la relación competitiva óptima es solo ligeramente sublineal. [27] Sin embargo, para los gráficos de intervalo , es posible una relación competitiva constante, [28] mientras que para los gráficos bipartitos y los gráficos dispersos se puede lograr una relación logarítmica. De hecho, para gráficos dispersos, la estrategia de coloración codiciosa estándar de elegir el primer color disponible logra esta relación competitiva, y es posible demostrar un límite inferior coincidente en la relación competitiva de cualquier algoritmo de coloración en línea. [26]
Coloración parsimonous
Una coloración parsimoniosa , para un gráfico y un orden de vértices dados, se ha definido como una coloración producida por un algoritmo codicioso que colorea los vértices en el orden dado, y solo introduce un nuevo color cuando todos los colores anteriores son adyacentes al vértice dado. pero puede elegir qué color usar (en lugar de elegir siempre el más pequeño) cuando puede reutilizar un color existente. El número cromático ordenado es el número más pequeño de colores que se puede obtener para el orden dado de esta manera, y el número ocromático es el número cromático ordenado más grande entre todos los colores de vértice de un gráfico dado. A pesar de su diferente definición, el número ocromático siempre es igual al número de Grundy. [29]
Aplicaciones
Debido a que es rápido y en muchos casos puede usar pocos colores, la coloración codiciosa se puede usar en aplicaciones donde se necesita una coloración de gráficos buena pero no óptima. Una de las primeras aplicaciones del algoritmo codicioso fue para problemas como la programación de cursos, en los que se debe asignar una colección de tareas a un conjunto determinado de intervalos de tiempo, evitando que las tareas incompatibles se asignen al mismo intervalo de tiempo. [4] También se puede utilizar en compiladores para la asignación de registros , aplicándolo a un gráfico cuyos vértices representan valores a asignar a registros y cuyas aristas representan conflictos entre dos valores que no pueden asignarse al mismo registro. [30] En muchos casos, estos gráficos de interferencia son gráficos cordales , lo que permite una coloración codiciosa para producir una asignación de registro óptima. [31]
En la teoría combinatoria de juegos , para un juego imparcial dado en forma explícita como un gráfico acíclico dirigido cuyos vértices representan posiciones de juego y cuyos bordes representan movimientos válidos de una posición a otra, el algoritmo codicioso de coloración (usando el reverso de un orden topológico del gráfico ) calcula el valor nim de cada posición. Estos valores se pueden utilizar para determinar el juego óptimo en cualquier juego único o en cualquier suma disyuntiva de juegos. [32]
Para un gráfico de grado máximo Δ , cualquier colorante codicioso utilizará como máximo Δ + 1 colores. El teorema de Brooks establece que con dos excepciones ( camarillas y ciclos impares ) como máximo se necesitan colores Δ . Una prueba del teorema de Brooks implica encontrar un orden de vértices en el que los dos primeros vértices son adyacentes al vértice final pero no adyacentes entre sí, y cada vértice que no sea el último tiene al menos un vecino posterior. Para un pedido con esta propiedad, el algoritmo de coloración codicioso utiliza como máximo colores Δ . [33]
Notas
- ^ Mitchem (1976) .
- ↑ a b Hoàng y Sritharan (2016) , Teorema 28.33, p. 738 ; Husfeldt (2015) , algoritmo G
- ↑ a b Frieze y McDiarmid (1997) .
- ↑ a b Welsh y Powell (1967) .
- ^ Johnson (1974) ; Husfeldt (2015) .
- ^ Kučera (1991) ; Husfeldt (2015) .
- ^ Husfeldt (2015) .
- ^ Maffray (2003) .
- ^ Rose, Lueker y Tarjan (1976) .
- ^ Chvátal (1984) ; Husfeldt (2015) .
- ^ Middendorf y Pfeiffer (1990) .
- ↑ a b c d Zaker (2006) .
- ^ Christen y Selkow (1979) .
- ^ Mitchem (1976) ; Husfeldt (2015) .
- ^ Matula y Beck (1983) .
- ^ Galés y Powell (1967) ; Husfeldt (2015) .
- ^ Matula (1968) ; Szekeres y Wilf (1968) .
- ↑ a b Kosowski y Manuszewski (2004) .
- ^ Markossian, Gasparian y Reed (1996) ; Maffray (2003) .
- ^ Markossian, Gasparian y Reed (1996) .
- ^ Gräf, Stumpf y Weißenfels (1998) .
- ^ Brélaz (1979) ; Lévêque y Maffray (2005) .
- ^ Brélaz (1979) .
- ^ Janczewski y col. (2001) .
- ^ Lévêque y Maffray (2005) .
- ↑ a b Irani (1994) .
- ^ Lovász, Saks y Trotter (1989) ; Vishwanathan (1992) .
- ^ Kierstead y Trotter (1981) .
- ^ Simmons (1982) ; Erdős y col. (1987) .
- ^ Poletto y Sarkar (1999) . Aunque Poletto y Sarkar describen que su método de asignación de registros no se basa en la coloración de gráficos, parece ser lo mismo que la coloración codiciosa.
- ^ Pereira y Palsberg (2005) .
- ^ Por ejemplo, consulte la Sección 1.1 de Nivasch (2006) .
- ^ Lovász (1975) .
Referencias
- Brélaz, Daniel (abril de 1979), "Nuevos métodos para colorear los vértices de un gráfico", Comunicaciones del ACM , 22 (4): 251-256, doi : 10.1145 / 359094.359101
- Christen, Claude A .; Selkow, Stanley M. (1979), "Algunas propiedades de coloración perfectas de los gráficos", Journal of Combinatorial Theory , Serie B, 27 (1): 49–59, doi : 10.1016 / 0095-8956 (79) 90067-4 , MR 0539075
- Chvátal, Václav (1984), "Gráficos perfectamente ordenables", en Berge, Claude ; Chvátal, Václav (eds.), Topics in Perfect Graphs , Annals of Discrete Mathematics, 21 , Amsterdam: North-Holland, págs. 63–68. Como lo cita Maffray (2003) .
- Erdős, P .; Liebre, WR; Hedetniemi, ST; Laskar, R. (1987), "Sobre la igualdad de los números de Grundy y ocromáticos de un gráfico" (PDF) , Journal of Graph Theory , 11 (2): 157-159, doi : 10.1002 / jgt.3190110205 , MR 0889347.
- Frieze, Alan ; McDiarmid, Colin (1997), "Teoría algorítmica de gráficos aleatorios", Estructuras y algoritmos aleatorios , 10 (1–2): 5–42, doi : 10.1002 / (SICI) 1098-2418 (199701/03) 10: 1 / 2 <5 :: AID-RSA2> 3.3.CO; 2-6 , MR 1611517.
- Gräf, A .; Stumpf, M .; Weißenfels, G. (1998), "On coloring unit disk graphs", Algorithmica , 20 (3): 277-293, doi : 10.1007 / PL00009196 , MR 1489033.
- Hoàng, Chinh T .; Sritharan, R. (2016), "Capítulo 28. Gráficos perfectos", en Thulasiraman, Krishnaiyan; Arumugam, subramaniano; Brandstädt, Andreas; Nishizeki, Takao (eds.), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms , Chapman & Hall / CRC Computer and Information Science Series, 34 , CRC Press, págs. 707–750, ISBN 9781420011074.
- Husfeldt, Thore (2015), "Algoritmos de coloración de gráficos", en Beineke, Lowell W .; Wilson, Robin J. (eds.), Temas de teoría de gráficos cromáticos , Encyclopedia of Mathematics and its Applications, 156 , Cambridge University Press, págs. 277-303, arXiv : 1505.05825 , MR 3380176
- Irani, Sandy (1994), "Colorear gráficos inductivos en línea", Algorithmica , 11 (1): 53–72, doi : 10.1007 / BF01294263 , MR 1247988.
- Janczewski, R .; Kubale, M .; Manuszewski, K .; Piwakowski, K. (2001), "El gráfico más pequeño y difícil de colorear para el algoritmo DSATUR", Matemáticas discretas , 236 (1-3): 151-165, doi : 10.1016 / S0012-365X (00) 00439-8 , Señor 1830607.
- Kierstead, HA; Trotter, WT (1981), "Un problema extremo en combinatoria recursiva", Actas de la Duodécima Conferencia del Sureste sobre Combinatoria, Teoría de Gráficos y Computación, vol. II (Baton Rouge, Luisiana, 1981), Congressus Numerantium , 33 : 143-153, MR 0681909. Como lo cita Irani (1994) .
- Kosowski, Adrian; Manuszewski, Krzysztof (2004), "Classical coloring of graphs", en Kubale, Marek (ed.), Graph Colorings , Contemporary Mathematics, 352 , Providence, Rhode Island: American Mathematical Society, págs. 1-19, doi : 10.1090 / conm / 352/06 369 , MR 2076987
- Kučera, Luděk (1991), "La coloración codiciosa es un mal algoritmo probabilístico", Journal of Algorithms , 12 (4): 674–684, doi : 10.1016 / 0196-6774 (91) 90040-6 , MR 1130323.
- Johnson, David S. (1974), "El peor comportamiento de los algoritmos de coloración de gráficos", Actas de la Quinta Conferencia Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Florida Atlantic Univ., Boca Raton, Fla., 1974) , Congressus Numerantium, X , Winnipeg, Manitoba: Utilitas Math., Págs. 513–527, MR 0389644.
- Lévêque, Benjamin; Maffray, Frédéric (octubre de 2005), "Colorear gráficos de Meyniel en tiempo lineal" (PDF) , en Raspaud, André; Delmas, Olivier (eds.), Séptimo Coloquio Internacional sobre Teoría de Gráficos (ICGT '05), 12-16 de septiembre de 2005, Hyeres, Francia , Electronic Notes in Discrete Mathematics, 22 , Elsevier, pp. 25-28, arXiv : cs / 0405059 , doi : 10.1016 / j.endm.2005.06.005. Ver también Lévêque, Benjamin; Maffray, Frédéric (9 de enero de 2006), Fe de erratas: MCColor no es óptimo en los gráficos de Meyniel , arXiv : cs / 0405059.
- Lovász, L. (1975), "Tres pruebas breves en la teoría de grafos", Journal of Combinatorial Theory , Serie B, 19 (3): 269-271, doi : 10.1016 / 0095-8956 (75) 90089-1 , MR 0396344.
- Lovász, L .; Saks, ME ; Trotter, WT (1989), "Un algoritmo de coloración de gráficos en línea con una relación de rendimiento sublineal", Matemáticas discretas , 75 (1–3): 319–325, doi : 10.1016 / 0012-365X (89) 90096-4 , MR 1001404.
- Maffray, Frédéric (2003), "Sobre la coloración de gráficos perfectos", en Reed, Bruce A .; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics , CMS Books in Mathematics, 11 , Springer-Verlag, págs. 65–84, doi : 10.1007 / 0-387-22444-0_3 , ISBN 0-387-95434-1, Señor 1952983.
- Markossian, SE; Gasparian, GS; Reed, BA (1996), "β-perfect graphs", Journal of Combinatorial Theory , Serie B, 67 (1): 1–11, doi : 10.1006 / jctb.1996.0030 , MR 1385380.
- Matula, David W. (1968), "Un teorema mínimo-máximo para gráficos con aplicación a la coloración de gráficos", Reunión Nacional SIAM 1968, Revisión SIAM , 10 (4): 481–482, doi : 10.1137 / 1010115.
- Matula, David W .; Beck, LL (1983), "Smallest-last ordering and clustering and graph colour algoritmos", Journal of the ACM , 30 (3): 417–427, doi : 10.1145 / 2402.322385 , MR 0709826.
- Middendorf, Matthias; Pfeiffer, Frank (1990), "Sobre la complejidad de reconocer gráficas perfectamente ordenables", Matemáticas discretas , 80 (3): 327–333, doi : 10.1016 / 0012-365X (90) 90251-C , MR 1049253.
- Mitchem, John (1976), "Sobre varios algoritmos para estimar el número cromático de un gráfico", The Computer Journal , 19 (2): 182-183, doi : 10.1093 / comjnl / 19.2.182 , MR 0437376.
- Nivasch, Gabriel (2006), "The Sprague-Grundy function of the game Euclid", Discrete Mathematics , 306 (21): 2798-2800, doi : 10.1016 / j.disc.2006.04.020 , MR 2264378.
- Pereira, Fernando Magno Quintão; Palsberg, Jens (2005), "Asignación de registros mediante la coloración de gráficos cordales", en Yi, Kwangkeun (ed.), Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japón, 2 al 5 de noviembre de 2005, Actas , Lecture Notes in Computer Science, 3780 , Springer, págs. 315–329, doi : 10.1007 / 11575467_21
- Poletto, Massimiliano; Sarkar, Vivek (septiembre de 1999), "Asignación de registros de exploración lineal", ACM Transactions on Programming Languages and Systems , 21 (5): 895–913, doi : 10.1145 / 330249.330250.
- Rose, D .; Lueker, George; Tarjan, Robert E. (1976), "Aspectos algorítmicos de la eliminación de vértices en gráficos", SIAM Journal on Computing , 5 (2): 266-283, doi : 10.1137 / 0205021 , MR 0408312.
- Simmons, Gustavus J. (1982), "El número cromático ordenado de mapas planos", Actas de la decimotercera conferencia del sureste sobre combinatoria, teoría de grafos y computación (Boca Raton, Florida, 1982), Congressus Numerantium , 36 : 59-67 , MR 0726050
- Sysło, Maciej M. (1989), "Coloración secuencial versus límite de Gales-Powell", Matemáticas discretas , 74 (1–2): 241–243, doi : 10.1016 / 0012-365X (89) 90212-4 , MR 0989136.
- Szekeres, George ; Wilf, Herbert S. (1968), "Una desigualdad para el número cromático de un gráfico", Journal of Combinatorial Theory , 4 : 1–3, doi : 10.1016 / S0021-9800 (68) 80081-X.
- Vishwanathan, Sundar (1992), "Coloración aleatoria de gráficos en línea", Journal of Algorithms , 13 (4): 657–669, doi : 10.1016 / 0196-6774 (92) 90061-G , MR 1187207.
- Galés, DJA ; Powell, MB (1967), "Un límite superior para el número cromático de un gráfico y su aplicación a problemas de horarios", The Computer Journal , 10 (1): 85–86, doi : 10.1093 / comjnl / 10.1.85.
- Zaker, Manouchehr (2006), "Results on the Grundy cromatic number of graphs", Discrete Mathematics , 306 (2–3): 3166–3173, doi : 10.1016 / j.disc.2005.06.044 , MR 2273147.