En teoría de grafos , el número de Grundy o número cromático de Grundy de un grafo no dirigido es el número máximo de colores que se pueden utilizar mediante una estrategia de coloración voraz que considera los vértices del grafo en secuencia y asigna a cada vértice su primer color disponible, utilizando un orden de vértices elegido para utilizar tantos colores como sea posible. Los números de Grundy reciben su nombre de PM Grundy , quien estudió un concepto análogo para grafos dirigidos en 1939. [1] La versión no dirigida fue introducida por Christen & Selkow (1979). [2]
El gráfico de trayectoria con cuatro vértices proporciona el ejemplo más simple de un gráfico cuyo número cromático difiere de su número de Grundy. Este gráfico se puede colorear con dos colores, pero su número de Grundy es tres: si se colorean primero los dos puntos finales de la trayectoria, el algoritmo de coloración voraz utilizará tres colores para todo el gráfico. [3]
Los grafos bipartitos completos son los únicos grafos conexos cuyo número de Grundy es dos. Todos los demás grafos conexos contienen un triángulo o un camino de cuatro vértices, lo que hace que el número de Grundy sea al menos tres. [3]
Los grafos de corona se obtienen a partir de grafos bipartitos completos eliminando un emparejamiento perfecto . Como resultado, para cada vértice en un lado de la bipartición, hay exactamente un vértice en el lado opuesto de la bipartición al que no es adyacente. Como grafos bipartitos, se pueden colorear con dos colores, pero su número de Grundy es : si un algoritmo de coloración voraz considera cada par de vértices emparejados en orden, cada par recibirá un color diferente. Como muestra este ejemplo, el número de Grundy puede ser mayor que el número cromático por un factor lineal en el número de vértices del grafo. [4]
Zaker (2006) define una secuencia de grafos llamada t -átomos , con la propiedad de que un grafo tiene número de Grundy al menos t si y solo si contiene un t -átomo. Cada t -átomo se forma a partir de un conjunto independiente y un ( t − 1) -átomo, añadiendo una arista de cada vértice del ( t − 1) -átomo a un vértice del conjunto independiente, de tal manera que cada miembro del conjunto independiente tiene al menos una arista incidente a él. Una coloración de Grundy de un t -átomo se puede obtener coloreando primero el conjunto independiente con el color de número más pequeño, y luego coloreando el ( t − 1) -átomo restante con t − 1 colores adicionales . Por ejemplo, el único átomo 1 es un único vértice, y el único átomo 2 es una única arista, pero hay dos posibles átomos 3: un triángulo y un camino de cuatro vértices. [3]
Para un grafo con n vértices y degeneración d , el número de Grundy es O ( d log n ) . En particular, para grafos de degeneración acotada (como grafos planares ) o grafos para los cuales el número cromático y la degeneración están acotados dentro de factores constantes entre sí (como grafos cordales ) el número de Grundy y el número cromático están dentro de un factor logarítmico entre sí. [5] Para grafos de intervalo , el número cromático y el número de Grundy están dentro de un factor de 8 entre sí. [6]
La comprobación de si el número de Grundy de un grafo dado es al menos k , para una constante fija k , se puede realizar en tiempo polinomial , buscando todos los k -átomos posibles que podrían ser subgrafos del grafo dado. Sin embargo, este algoritmo no es manejable con parámetros fijos , porque el exponente en su tiempo de ejecución depende de k . Cuando k es una variable de entrada en lugar de un parámetro, el problema es NP-completo . [3] El número de Grundy es como máximo uno más el grado máximo del grafo, y sigue siendo NP-completo comprobar si es igual a uno más el grado máximo. [7] Existe una constante c > 1 tal que es NP-difícil bajo reducciones aleatorias aproximar el número de Grundy dentro de una razón de aproximación mejor que c . [8]
Existe un algoritmo de tiempo exponencial exacto para el número de Grundy que se ejecuta en el tiempo O (2,443 n ) . [9]
Para árboles y grafos de ancho de árbol acotado , el número de Grundy puede ser ilimitadamente grande. [10] Sin embargo, el número de Grundy se puede calcular en tiempo polinomial para árboles, y es manejable con parámetros fijos cuando se parametriza tanto por el ancho de árbol como por el número de Grundy, [11] aunque (asumiendo la hipótesis de tiempo exponencial ) la dependencia del ancho de árbol debe ser mayor que la exponencial simple. [9] Cuando se parametriza solo por el número de Grundy, se puede calcular en tiempo manejable con parámetros fijos para grafos cordales y grafos sin garras , [9] y también (usando resultados generales sobre isomorfismo de subgrafos en grafos dispersos para buscar átomos) para grafos de expansión acotada . [9] [12] [13] Sin embargo, en grafos generales el problema es W[1]-duro cuando se parametriza por el número de Grundy. [14]
Se dice que un grafo está bien coloreado si su número de Grundy es igual a su número cromático. La comprobación de si un grafo está bien coloreado es coNP-completo. [3] Los grafos hereditariamente bien coloreados (grafos para los cuales cada subgrafo inducido está bien coloreado) son exactamente los cografos , los grafos que no tienen una ruta de cuatro vértices como subgrafo inducido. [2]
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )