Coloración voraz

En el estudio de los problemas de coloración de grafos en matemáticas y ciencias de la computación, una coloración voraz o coloración secuencial es una coloración de los vértices de un grafo obtenida mediante un algoritmo voraz que recorre los vértices del grafo en secuencia y asigna a cada vértice el primer color disponible. Las coloraciones voraces pueden encontrarse en tiempo lineal, pero en general no usan el menor número posible de colores.

Distintas elecciones de la secuencia de vértices suelen producir coloraciones distintas del mismo grafo, por lo que buena parte del estudio de las coloraciones voraces se ha ocupado de cómo encontrar un buen orden. Siempre existe un orden que produce una coloración óptima, pero, aunque es posible encontrar esos órdenes para muchas clases especiales de grafos, en general son difíciles de hallar. Las estrategias de ordenación más usadas consisten en colocar los vértices de mayor grado antes que los de menor grado, o en elegir primero los vértices con menos colores disponibles frente a los que están menos restringidos.

Algunas variantes de la coloración voraz eligen los colores de forma en línea, sin conocer la estructura de la parte del grafo que aún no está coloreada, o eligen colores distintos del primero disponible para reducir el número total de colores. Los algoritmos de coloración voraz se han aplicado a problemas de planificación de horarios y de asignación de registros, al análisis de juegos combinatorios y a las demostraciones de otros resultados matemáticos, entre ellos el teorema de Brooks sobre la relación entre la coloración y el grado. Otros conceptos de la teoría de grafos derivados de las coloraciones voraces son el número de Grundy de un grafo (el mayor número de colores que puede obtener una coloración voraz) y los grafos bien coloreados, aquellos en los que todas las coloraciones voraces usan el mismo número de colores.

Algoritmo

La coloración voraz correspondiente a un orden dado de los vértices puede calcularse con un algoritmo que se ejecuta en tiempo lineal. El algoritmo procesa los vértices en el orden dado y asigna un color a cada uno a medida que lo procesa. Los colores pueden representarse con los números $0,1,2,\dots$ , y a cada vértice se le asigna el color con el menor número que no use ya alguno de sus vecinos. Para encontrar el menor color disponible, se puede usar un arreglo que cuente el número de vecinos de cada color (o bien que represente el conjunto de colores de los vecinos) y luego recorrer el arreglo para hallar el índice de su primer cero.

En Python, el algoritmo puede expresarse así:

def first_available(colors):
    """Devuelve el menor entero no negativo que no está en el conjunto de colores dado.
    """
    color = 0
    while color in colors:
        color += 1
    return color

def greedy_coloring(G, order):
    """Calcula la coloración voraz de G en el orden dado.

    Se supone que G se representa como en
    https://www.python.org/doc/essays/graphs/
    de modo que los vecinos de un nodo o vértice pueden
    recorrerse con "for w in G[node]".
    El valor devuelto es un diccionario que asigna un color a cada vértice.
    """
    coloring = dict()
    for node in order:
        used_neighbour_colors = {coloring[nbr]
                                 for nbr in G[node]
                                 if nbr in coloring}
        coloring[node] = first_available(used_neighbour_colors)
    return coloring

La búsqueda del primer color disponible (la subrutina first_available) puede hacerse en un tiempo proporcional a la longitud de su lista de argumentos, mediante dos recorridos: uno sobre la propia lista y otro sobre un arreglo de conteos de la misma longitud. El tiempo del algoritmo de coloración completo está dominado por las llamadas a esta subrutina. Cada arista del grafo contribuye a una sola de estas llamadas: la del extremo de la arista que aparece más tarde en el orden de los vértices. Por lo tanto, la suma de las longitudes de las listas de argumentos de first_available, y el tiempo total del algoritmo, son proporcionales al número de aristas del grafo.

Un algoritmo alternativo, que produce la misma coloración, consiste en elegir los conjuntos de vértices de cada color, un color cada vez. En este método, cada clase de color $C$ se elige recorriendo los vértices en el orden dado. Cuando el recorrido encuentra un vértice sin colorear $v$ que no tiene ningún vecino en $C$ , añade $v$ a $C$ . De este modo, $C$ pasa a ser un conjunto independiente maximal entre los vértices a los que todavía no se les han asignado colores menores. El algoritmo va encontrando clases de color de esta manera hasta que todos los vértices están coloreados. Sin embargo, requiere varios recorridos del grafo, uno por cada clase de color, en lugar del único recorrido del método descrito antes.

Elección del orden

Distintos órdenes de los vértices de un grafo pueden hacer que la coloración voraz use distinto número de colores, desde el número óptimo hasta, en algunos casos, un número de colores proporcional al número de vértices del grafo. Por ejemplo, un grafo corona (un grafo formado a partir de dos conjuntos disjuntos de $n /2$ vértices ${a 1, a 2, ...$ } y ${b 1, b 2, ...$ }, uniendo $a i$ con $b j$ siempre que $i \neq j$ ) puede ser un caso especialmente desfavorable para la coloración voraz. Con el orden de vértices $a 1, b 1, a 2, b 2, ...$ , una coloración voraz usa $n /2$ colores, uno para cada par $(a i, b i)$ . Sin embargo, el número óptimo de colores para este grafo es dos: un color para los vértices $a i$ y otro para los vértices $b i$ . También existen grafos en los que, con alta probabilidad, un orden de vértices elegido al azar da lugar a un número de colores mucho mayor que el mínimo. Por ello, en la coloración voraz tiene cierta importancia elegir con cuidado el orden de los vértices.

Órdenes buenos

Los vértices de cualquier grafo pueden ordenarse siempre de forma que el algoritmo voraz produzca una coloración óptima. En efecto, dada cualquier coloración óptima, se pueden ordenar los vértices según sus colores; si luego se aplica el algoritmo voraz con ese orden, la coloración resultante es automáticamente óptima. Sin embargo, como la coloración óptima de grafos es NP-completa, cualquier subproblema que permitiera resolver rápidamente este problema, incluido el de encontrar un orden óptimo para la coloración voraz, es NP-difícil.

En los grafos de intervalos y los grafos cordales, si los vértices se ordenan en el orden inverso de un orden de eliminación perfecta, los vecinos anteriores de cada vértice forman un clique. Gracias a esta propiedad, la coloración voraz produce una coloración óptima, porque nunca usa más colores de los necesarios para cada uno de esos cliques. Un orden de eliminación puede encontrarse en tiempo lineal, cuando existe.

Más aún, cualquier orden de eliminación perfecta es hereditariamente óptimo, es decir, es óptimo tanto para el propio grafo como para todos sus subgrafos inducidos. Los grafos perfectamente ordenables (entre los que se encuentran los grafos cordales, los grafos de comparabilidad y los grafos con herencia de distancias) se definen como los grafos que tienen un orden hereditariamente óptimo. Reconocer los grafos perfectamente ordenables también es NP-completo.

Órdenes malos

El número de colores que produce la coloración voraz con el peor orden de un grafo dado se llama su número de Grundy. Al igual que es difícil encontrar un buen orden de los vértices para la coloración voraz, también lo es encontrar uno malo. Determinar, para un grafo $G$ y un número $k$ dados, si existe un orden de los vértices de $G$ que haga que el algoritmo voraz use $k$ o más colores es un problema NP-completo. En particular, esto significa que es difícil encontrar el peor orden para $G$ .

Grafos en los que el orden es irrelevante

Los grafos bien coloreados son aquellos en los que todos los órdenes de los vértices producen el mismo número de colores. En estos grafos, ese número de colores es igual tanto al número cromático como al número de Grundy. Entre ellos se encuentran los cografos, que son exactamente los grafos cuyos subgrafos inducidos son todos bien coloreados. Sin embargo, determinar si un grafo está bien coloreado es co-NP-completo.

Si se toma un grafo aleatorio del modelo de Erdős–Rényi con una probabilidad constante de incluir cada arista, cualquier orden de los vértices elegido con independencia de las aristas del grafo da lugar, con alta probabilidad, a una coloración cuyo número de colores es cercano al doble del valor óptimo. Se desconoce si existe algún método de tiempo polinómico que encuentre coloraciones significativamente mejores de estos grafos.

Degeneración

Como los órdenes óptimos de los vértices son difíciles de encontrar, se han usado heurísticas que intentan reducir el número de colores sin garantizar un número óptimo. Un orden muy usado para la coloración voraz consiste en elegir un vértice $v$ de grado mínimo, ordenar recursivamente el subgrafo que queda al quitar $v$ y colocar después $v$ al final del orden. El mayor grado de un vértice eliminado que encuentra este algoritmo se llama la degeneración del grafo y se denota $d$ . En el contexto de la coloración voraz, esta misma estrategia de ordenación también se llama orden del «menor al final» (smallest last). Este orden de los vértices, y la degeneración, pueden calcularse en tiempo lineal. Puede verse como una versión mejorada de un método de ordenación anterior, el orden del «mayor primero» (largest first), que ordena los vértices de forma decreciente según su grado.

Con el orden de degeneración, la coloración voraz usa como máximo $d + 1$ colores. Esto se debe a que, en el momento de colorearlo, cada vértice tiene como máximo $d$ vecinos ya coloreados, por lo que uno de los primeros $d + 1$ colores queda libre para él. La coloración voraz con el orden de degeneración puede encontrar coloraciones óptimas para ciertas clases de grafos, como los árboles, los pseudobosques y los grafos corona. Markossian, Gasparian y Reed (1996) definen un grafo $G$ como $\beta$ -perfecto si, para $G$ y para cada subgrafo inducido de $G$ , el número cromático es igual a la degeneración más uno. Para estos grafos, el algoritmo voraz con el orden de degeneración es siempre óptimo. Todo grafo $\beta$ -perfecto debe ser un grafo sin agujeros pares, porque los ciclos pares tienen número cromático dos y degeneración dos, lo que no cumple la igualdad de la definición de grafo $\beta$ -perfecto. Si un grafo y su grafo complemento son ambos sin agujeros pares, los dos son $\beta$ -perfectos. Los grafos que son a la vez grafos perfectos y $\beta$ -perfectos son exactamente los grafos cordales. En los grafos sin agujeros pares en general, el orden de degeneración aproxima la coloración óptima con, como mucho, el doble del número óptimo de colores; es decir, su razón de aproximación es 2. El prisma triangular es el grafo más pequeño en el que uno de sus órdenes de degeneración da lugar a una coloración no óptima, y el antiprisma cuadrado es el grafo más pequeño que no puede colorearse de forma óptima con ninguno de sus órdenes de degeneración.

Órdenes adaptativos

Brélaz (1979) propone una estrategia, llamada DSatur, para ordenar los vértices en la coloración voraz que intercala la construcción del orden con el proceso de coloración. En su versión del algoritmo de coloración voraz, el siguiente vértice que se colorea en cada paso es el que tiene el mayor número de colores distintos en su vecindad. En caso de empate, se elige entre los vértices empatados uno de grado máximo en el subgrafo de los vértices sin colorear. Si se lleva la cuenta, en cada paso, de los conjuntos de colores vecinos y de sus cardinales, es posible implementar este método en tiempo lineal.

Este método puede encontrar coloraciones óptimas para los grafos bipartitos, todos los grafos cactus, todos los grafos rueda, todos los grafos de seis vértices como máximo y casi todos los grafos $k$ -coloreables. Aunque Lévêque y Maffray (2005) afirmaron en un principio que este método encuentra coloraciones óptimas para los grafos de Meyniel, más tarde encontraron un contraejemplo a esa afirmación.

Otros criterios de elección del color

Es posible definir variantes del algoritmo de coloración voraz en las que los vértices del grafo se colorean en una secuencia dada, pero el color elegido para cada vértice no es necesariamente el primero disponible. Entre ellas hay métodos en los que el algoritmo desconoce la parte del grafo que aún no está coloreada, o en los que el algoritmo tiene cierta libertad para elegir colores mejores que los que elegiría el algoritmo voraz básico.

Elección en línea

Se han estudiado otras estrategias de elección del color en el marco de los algoritmos en línea. En el problema de coloración de grafos en línea, los vértices de un grafo se presentan uno a uno, 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 de los vértices ya procesados y en las adyacencias entre ellos. En este contexto, la calidad de una estrategia de elección del color se mide por su razón competitiva, el cociente entre el número de colores que usa y el número óptimo de colores para el grafo dado.

Si no se imponen restricciones adicionales al grafo, la razón competitiva óptima es solo ligeramente sublineal. Sin embargo, para los grafos de intervalos es posible una razón competitiva constante, mientras que para los grafos bipartitos y los grafos dispersos se puede lograr una razón logarítmica. De hecho, para los grafos dispersos, la estrategia voraz habitual de elegir el primer color disponible alcanza esta razón competitiva, y es posible demostrar una cota inferior equivalente para la razón competitiva de cualquier algoritmo de coloración en línea.

Coloración parsimoniosa

Una coloración parsimoniosa, para un grafo y un orden de los vértices dados, se ha definido como una coloración producida por un algoritmo voraz que colorea los vértices en el orden dado y que solo introduce un color nuevo cuando todos los colores anteriores son adyacentes al vértice en cuestión, pero que puede elegir qué color usar (en lugar de elegir siempre el menor) cuando puede reutilizar un color existente. El número cromático ordenado es el menor número de colores que puede obtenerse de esta manera para el orden dado, y el número ocromático es el mayor número cromático ordenado entre todos los órdenes de los vértices de un grafo dado. Pese a su definición distinta, el número ocromático es siempre igual al número de Grundy.

Aplicaciones

Como es rápida y en muchos casos puede usar pocos colores, la coloración voraz puede emplearse en aplicaciones en las que se necesita una coloración de grafos buena, aunque no óptima. Una de las primeras aplicaciones del algoritmo voraz fue en problemas como la planificación de horarios de cursos, en los que un conjunto de tareas debe asignarse a un conjunto dado de franjas horarias evitando que se asignen tareas incompatibles a la misma franja. También puede usarse en los compiladores para la asignación de registros, aplicándola a un grafo cuyos vértices representan valores que deben asignarse a registros y cuyas aristas representan conflictos entre dos valores que no pueden asignarse al mismo registro. En muchos casos, estos grafos de interferencia son grafos cordales, lo que permite que la coloración voraz produzca una asignación de registros óptima.

En la teoría de juegos combinatorios, para un juego imparcial dado de forma explícita como un grafo acíclico dirigido cuyos vértices representan las posiciones del juego y cuyas aristas representan los movimientos válidos de una posición a otra, el algoritmo de coloración voraz (con el orden inverso de un ordenamiento topológico del grafo) calcula el valor de nim de cada posición. Estos valores pueden usarse para determinar la estrategia óptima en cualquier juego individual o en cualquier suma disyuntiva de juegos.

Para un grafo de grado máximo $Δ$ , cualquier coloración voraz usa como máximo $Δ + 1$ colores. El teorema de Brooks establece que, con dos excepciones (los cliques y los ciclos impares), bastan como máximo $Δ$ colores. Una de las demostraciones del teorema de Brooks consiste en encontrar un orden de los vértices en el que los dos primeros vértices son adyacentes al último pero no entre sí, y en el que cada vértice distinto del último tiene al menos un vecino posterior. Con un orden que cumple esta propiedad, el algoritmo de coloración voraz usa como máximo $Δ$ colores.

Referencias

↑ Mitchem, 1976.
1 2 Husfeldt, 2015.
1 2 Hoàng y Sritharan (2016), teorema 28.33, p. 738; Husfeldt (2015), algoritmo G.
1 2 Frieze y McDiarmid, 1997.
1 2 Welsh y Powell, 1967.
↑ Johnson (1974); Husfeldt (2015).
↑ Kučera (1991); Husfeldt (2015).
↑ Maffray, 2003.
↑ Rose, Lueker y Tarjan, 1976.
↑ Chvátal (1984); Husfeldt (2015).
↑ Middendorf y Pfeiffer, 1990.
1 2 3 4 Zaker, 2006.
↑ Christen y Selkow, 1979.
↑ Mitchem (1976); Husfeldt (2015).
↑ Matula y Beck, 1983.
↑ Welsh y Powell (1967); Husfeldt (2015).
↑ Matula (1968); Szekeres y Wilf (1968).
1 2 Kosowski y Manuszewski, 2004.
↑ Markossian, Gasparian y Reed (1996); Maffray (2003).
↑ Markossian, Gasparian y Reed, 1996.
↑ Brélaz (1979); Lévêque y Maffray (2005).
↑ Brélaz, 1979.
↑ Janczewski et al., 2001.
↑ Lévêque y Maffray, 2005.
1 2 Irani, 1994.
↑ Lovász, Saks y Trotter (1989); Vishwanathan (1992).
↑ Kierstead y Trotter, 1981.
↑ Simmons (1982); Erdős et al. (1987).
↑ Poletto y Sarkar (1999). Aunque Poletto y Sarkar describen su método de asignación de registros como no basado en la coloración de grafos, parece ser lo mismo que la coloración voraz.
↑ Pereira y Palsberg, 2005.
↑ Véase, por ejemplo, la sección 1.1 de Nivasch (2006).
↑ Lovász, 1975.

Bibliografía

Brélaz, Daniel (1979). «New methods to color the vertices of a graph» [Nuevos métodos para colorear los vértices de un grafo]. Communications of the ACM 22 (4): 251-256. S2CID 14838769. doi:10.1145/359094.359101.
Christen, Claude A.; Selkow, Stanley M. (1979). «Some perfect coloring properties of graphs» [Algunas propiedades de coloración perfecta de los grafos]. Journal of Combinatorial Theory, Series B 27 (1): 49-59. MR 539075. doi:10.1016/0095-8956(79)90067-4.
Chvátal, Václav (1984). «Perfectly orderable graphs». En Berge, Claude; Chvátal, Václav, eds. Topics in Perfect Graphs [Grafos perfectamente ordenables]. Annals of Discrete Mathematics 21. Ámsterdam: North-Holland. pp. 63-68. Citado por Maffray (2003).
Erdős, P.; Hare, W. R.; Hedetniemi, S. T.; Laskar, R. (1987). «On the equality of the Grundy and ochromatic numbers of a graph» [Sobre la igualdad de los números de Grundy y ocromático de un grafo]. Journal of Graph Theory 11 (2): 157-159. MR 889347. doi:10.1002/jgt.3190110205.
Frieze, Alan; McDiarmid, Colin (1997). «Algorithmic theory of random graphs» [Teoría algorítmica de los grafos aleatorios]. Random Structures & Algorithms 10 (1-2): 5-42. MR 1611517. doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.3.CO;2-6.
Hoàng, Chinh T.; Sritharan, R. (2016). «Chapter 28. Perfect Graphs». En Thulasiraman, Krishnaiyan; Arumugam, Subramanian; Brandstädt, Andreas; Nishizeki, Takao, eds. Handbook of Graph Theory, Combinatorial Optimization, and Algorithms [Capítulo 28. Grafos perfectos]. Chapman & Hall/CRC Computer and Information Science Series 34. CRC Press. pp. 707-750. ISBN 9781420011074.
Husfeldt, Thore (2015). «Graph colouring algorithms». En Beineke, Lowell W.; Wilson, Robin J., eds. Topics in Chromatic Graph Theory [Algoritmos de coloración de grafos]. Encyclopedia of Mathematics and its Applications 156. Cambridge University Press. pp. 277-303. MR 3380176. arXiv:1505.05825.
Irani, Sandy (1994). «Coloring inductive graphs on-line» [Coloración en línea de grafos inductivos]. Algorithmica 11 (1): 53-72. MR 1247988. S2CID 181800. doi:10.1007/BF01294263.
Janczewski, R.; Kubale, M.; Manuszewski, K.; Piwakowski, K. (2001). «The smallest hard-to-color graph for algorithm DSATUR» [El grafo difícil de colorear más pequeño para el algoritmo DSATUR]. Discrete Mathematics 236 (1-3): 151-165. MR 1830607. doi:10.1016/S0012-365X(00)00439-8.
Kierstead, H. A.; Trotter, W. T. (1981). «An extremal problem in recursive combinatorics» [Un problema extremal en combinatoria recursiva]. Congressus Numerantium 33: 143-153. MR 0681909. Actas de la duodécima Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. II (Baton Rouge, 1981). Citado por Irani (1994).
Kosowski, Adrian; Manuszewski, Krzysztof (2004). «Classical coloring of graphs». En Kubale, Marek, ed. Graph Colorings [Coloración clásica de grafos]. Contemporary Mathematics 352. Providence (Rhode Island): American Mathematical Society. pp. 1-19. ISBN 978-0-8218-3458-9. MR 2076987. doi:10.1090/conm/352/06369.
Kučera, Luděk (1991). «The greedy coloring is a bad probabilistic algorithm» [La coloración voraz es un mal algoritmo probabilístico]. Journal of Algorithms 12 (4): 674-684. MR 1130323. doi:10.1016/0196-6774(91)90040-6.
Johnson, David S. (1974). «Worst case behavior of graph coloring algorithms». Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974) [Comportamiento en el peor caso de los algoritmos de coloración de grafos]. Congressus Numerantium X. Winnipeg (Manitoba): Utilitas Math. pp. 513-527. MR 0389644.
Lévêque, Benjamin; Maffray, Frédéric (2005). «Coloring Meyniel graphs in linear time». En Raspaud, André; Delmas, Olivier, eds. 7th International Colloquium on Graph Theory (ICGT '05), 12–16 September 2005, Hyeres, France [Coloración de grafos de Meyniel en tiempo lineal]. Electronic Notes in Discrete Mathematics 22. Elsevier. pp. 25-28. S2CID 6262680. arXiv:cs/0405059. doi:10.1016/j.endm.2005.06.005. Véase también «Erratum: MCColor is not optimal on Meyniel graphs». arXiv:cs/0405059. 9 de enero de 2006. .
Lovász, L. (1975). «Three short proofs in graph theory» [Tres demostraciones breves en teoría de grafos]. Journal of Combinatorial Theory, Series B 19 (3): 269-271. MR 0396344. doi:10.1016/0095-8956(75)90089-1.
Lovász, L.; Saks, M. E.; Trotter, W. T. (1989). «An on-line graph coloring algorithm with sublinear performance ratio» [Un algoritmo de coloración de grafos en línea con razón de rendimiento sublineal]. Discrete Mathematics 75 (1-3): 319-325. MR 1001404. doi:10.1016/0012-365X(89)90096-4.
Maffray, Frédéric (2003). «On the coloration of perfect graphs». En Reed, Bruce A.; Sales, Cláudia L., eds. Recent Advances in Algorithms and Combinatorics [Sobre la coloración de los grafos perfectos]. CMS Books in Mathematics 11. Springer-Verlag. pp. 65-84. ISBN 0-387-95434-1. MR 1952983. doi:10.1007/0-387-22444-0_3.
Markossian, S. E.; Gasparian, G. S.; Reed, B. A. (1996). «β-perfect graphs» [Grafos β-perfectos]. Journal of Combinatorial Theory, Series B 67 (1): 1-11. MR 1385380. doi:10.1006/jctb.1996.0030.
Matula, David W. (1968). «A min-max theorem for graphs with application to graph coloring» [Un teorema minimax para grafos con aplicación a la coloración de grafos]. SIAM Review 10 (4): 481-482. doi:10.1137/1010115. Resumen presentado en el SIAM 1968 National Meeting.
Matula, David W.; Beck, L. L. (1983). «Smallest-last ordering and clustering and graph coloring algorithms» [El orden del menor al final y los algoritmos de agrupamiento y de coloración de grafos]. Journal of the ACM 30 (3): 417-427. MR 0709826. doi:10.1145/2402.322385.
Middendorf, Matthias; Pfeiffer, Frank (1990). «On the complexity of recognizing perfectly orderable graphs» [Sobre la complejidad de reconocer los grafos perfectamente ordenables]. Discrete Mathematics 80 (3): 327-333. MR 1049253. doi:10.1016/0012-365X(90)90251-C.
Mitchem, John (1976). «On various algorithms for estimating the chromatic number of a graph» [Sobre varios algoritmos para estimar el número cromático de un grafo]. The Computer Journal 19 (2): 182-183. MR 0437376. doi:10.1093/comjnl/19.2.182.
Nivasch, Gabriel (2006). «The Sprague–Grundy function of the game Euclid» [La función de Sprague-Grundy del juego Euclides]. Discrete Mathematics 306 (21): 2798-2800. MR 2264378. doi:10.1016/j.disc.2006.04.020.
Pereira, Fernando Magno Quintão; Palsberg, Jens (2005). «Register allocation via coloring of chordal graphs». En Yi, Kwangkeun, ed. Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2–5, 2005, Proceedings [Asignación de registros mediante la coloración de grafos cordales]. Lecture Notes in Computer Science 3780. Springer. pp. 315-329. ISBN 978-3-540-29735-2. doi:10.1007/11575467_21.
Poletto, Massimiliano; Sarkar, Vivek (1999). «Linear scan register allocation» [Asignación de registros por barrido lineal]. ACM Transactions on Programming Languages and Systems 21 (5): 895-913. S2CID 18180752. doi:10.1145/330249.330250.
Rose, D.; Lueker, George; Tarjan, Robert E. (1976). «Algorithmic aspects of vertex elimination on graphs» [Aspectos algorítmicos de la eliminación de vértices en grafos]. SIAM Journal on Computing 5 (2): 266-283. MR 0408312. doi:10.1137/0205021.
Simmons, Gustavus J. (1982). «The ordered chromatic number of planar maps» [El número cromático ordenado de los mapas planos]. Congressus Numerantium 36: 59-67. MR 726050. Actas de la decimotercera Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Ratón, 1982).
Szekeres, George; Wilf, Herbert S. (1968). «An inequality for the chromatic number of a graph» [Una desigualdad para el número cromático de un grafo]. Journal of Combinatorial Theory 4: 1-3. doi:10.1016/S0021-9800(68)80081-X.
Vishwanathan, Sundar (1992). «Randomized online graph coloring» [Coloración aleatorizada de grafos en línea]. Journal of Algorithms 13 (4): 657-669. MR 1187207. doi:10.1016/0196-6774(92)90061-G.
Welsh, D. J. A.; Powell, M. B. (1967). «An upper bound for the chromatic number of a graph and its application to timetabling problems» [Una cota superior para el número cromático de un grafo y su aplicación a los problemas de horarios]. The Computer Journal 10 (1): 85-86. doi:10.1093/comjnl/10.1.85.
Zaker, Manouchehr (2006). «Results on the Grundy chromatic number of graphs» [Resultados sobre el número cromático de Grundy de los grafos]. Discrete Mathematics 306 (23): 3166-3173. MR 2273147. doi:10.1016/j.disc.2005.06.044.

Datos: Q5601715

[FOOTNOTEMitchem1976-1] Mitchem, 1976.

[FOOTNOTEHusfeldt2015-2] 1 2 Husfeldt, 2015.

[hs-3] 1 2 Hoàng y Sritharan (2016), teorema 28.33, p. 738; Husfeldt (2015), algoritmo G.

[FOOTNOTEFriezeMcDiarmid1997-4] 1 2 Frieze y McDiarmid, 1997.

[FOOTNOTEWelshPowell1967-5] 1 2 Welsh y Powell, 1967.

[6] Johnson (1974); Husfeldt (2015).

[7] Kučera (1991); Husfeldt (2015).

[FOOTNOTEMaffray2003-8] Maffray, 2003.

[FOOTNOTERoseLuekerTarjan1976-9] Rose, Lueker y Tarjan, 1976.

[10] Chvátal (1984); Husfeldt (2015).

[FOOTNOTEMiddendorfPfeiffer1990-11] Middendorf y Pfeiffer, 1990.

[FOOTNOTEZaker2006-12] 1 2 3 4 Zaker, 2006.

[FOOTNOTEChristenSelkow1979-13] Christen y Selkow, 1979.

[14] Mitchem (1976); Husfeldt (2015).

[FOOTNOTEMatulaBeck1983-15] Matula y Beck, 1983.

[16] Welsh y Powell (1967); Husfeldt (2015).

[17] Matula (1968); Szekeres y Wilf (1968).

[FOOTNOTEKosowskiManuszewski2004-18] 1 2 Kosowski y Manuszewski, 2004.

[19] Markossian, Gasparian y Reed (1996); Maffray (2003).

[FOOTNOTEMarkossianGasparianReed1996-20] Markossian, Gasparian y Reed, 1996.

[21] Brélaz (1979); Lévêque y Maffray (2005).

[FOOTNOTEBrélaz1979-22] Brélaz, 1979.

[FOOTNOTEJanczewskiKubaleManuszewskiPiwakowski2001-23] Janczewski et al., 2001.

[FOOTNOTELévêqueMaffray2005-24] Lévêque y Maffray, 2005.

[FOOTNOTEIrani1994-25] 1 2 Irani, 1994.

[26] Lovász, Saks y Trotter (1989); Vishwanathan (1992).

[FOOTNOTEKiersteadTrotter1981-27] Kierstead y Trotter, 1981.

[28] Simmons (1982); Erdős et al. (1987).

[29] Poletto y Sarkar (1999). Aunque Poletto y Sarkar describen su método de asignación de registros como no basado en la coloración de grafos, parece ser lo mismo que la coloración voraz.

[FOOTNOTEPereiraPalsberg2005-30] Pereira y Palsberg, 2005.

[31] Véase, por ejemplo, la sección 1.1 de Nivasch (2006).

[FOOTNOTELovász1975-32] Lovász, 1975.