En teoría de grafos , el número de Grundy o número cromático de Grundy de un gráfico no dirigido es el número máximo de colores que puede utilizar una estrategia de coloración codiciosa que considera los vértices del gráfico en secuencia y asigna a cada vértice su primer color disponible, utilizando un Ordenamiento de vértices elegido para utilizar tantos colores como sea posible. Los números de Grundy llevan el 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 y Selkow (1979). [2]
El gráfico de ruta 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 los dos puntos finales de la ruta se colorean primero, el algoritmo de coloración codiciosa utilizará tres colores para todo el gráfico. [3]
Los gráficos bipartitos completos son los únicos gráficos conectados cuyo número de Grundy es dos. Todos los demás gráficos conectados contienen un triángulo o una trayectoria de cuatro vértices, lo que hace que el número de Grundy sea al menos tres. [3]
Los gráficos de la corona se obtienen a partir de gráficos bipartitos completos eliminando una coincidencia perfecta . 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 gráficos bipartitos, se pueden colorear con dos colores, pero su número de Grundy es : si un algoritmo de coloración codicioso considera cada par de vértices coincidentes 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 en un factor lineal en el número de vértices del gráfico. [4]
Zaker (2006) define una secuencia de gráficos llamados t - átomos , con la propiedad de que un gráfico tiene un 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. Se puede obtener una coloración Grundy de un átomo t coloreando primero el conjunto independiente con el color con el número más pequeño y luego coloreando el átomo restante ( t − 1) con un color t − 1 adicional . Por ejemplo, el único átomo es un solo vértice, y el único átomo es un solo borde, pero hay dos posibles tres átomos: un triángulo y un camino de cuatro vértices. [3]
Para un gráfico con n vértices y degeneración d , el número de Grundy es O ( d log n ) . En particular, para gráficos de degeneración acotada (como gráficos planos ) o gráficos para los cuales el número cromático y la degeneración están acotados dentro de factores constantes entre sí (como gráficos cordales ), el número de Grundy y el número cromático están dentro de un factor logarítmico de cada uno. otro. [5] Para gráficos de intervalo , el número cromático y el número de Grundy están dentro de un factor de 8 entre sí. [6]
Probar si el número de Grundy de un gráfico dado es al menos k , para una constante fija k , se puede realizar en tiempo polinómico , buscando todos los k -átomos posibles que podrían ser subgrafos del gráfico 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 gráfico, y permanece NP-completo para probar 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 relació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 gráficos 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 del árbol como por el número de Grundy, [11] aunque (asumiendo la hipótesis del tiempo exponencial ) la dependencia del ancho del árbol debe ser mayor que simplemente exponencial. [9] Cuando está parametrizado solo por el número de Grundy, se puede calcular en tiempo manejable de parámetros fijos para gráficos cordales y gráficos sin garras , [9] y también (usando resultados generales sobre isomorfismo de subgrafos en gráficos dispersos para buscar átomos) para gráficas de expansión acotada . [9] [12] [13] Sin embargo, en gráficos generales el problema es W[1]-difícil cuando está parametrizado por el número de Grundy. [14]
Una gráfica se considera bien coloreada si su número de Grundy es igual a su número cromático. Probar si un gráfico está bien coloreado es coNP completo. [3] Los gráficos hereditariamente bien coloreados (gráficos en los que cada subgrafo inducido está bien coloreado) son exactamente los cografos , los gráficos que no tienen una trayectoria de cuatro vértices como subgrafo inducido. [2]
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )