Graficar familias que tienen algoritmos de tiempo polinomiales para calcular el número cromático

Publicación actualizada el 31 de agosto : agregué un resumen de las respuestas actuales debajo de la pregunta original. Gracias por todas las respuestas interesantes! Por supuesto, todos pueden seguir publicando cualquier hallazgo nuevo.

¿Para qué familias de gráficos existe un algoritmo de tiempo polinómico para calcular el número cromático ?$\chi(G)$

El problema se puede resolver en tiempo polinómico cuando (gráficos bipartitos). En general, cuando χ ( G ) ≥ 3 , calcular el número cromático es NP-duro, pero hay muchas familias de gráficos donde este no es el caso. Por ejemplo, los ciclos de coloración y los gráficos perfectos se pueden hacer en tiempo polinómico.$\chi(G) = 2$$\chi(G) \ge 3$

Además, para muchas clases de gráficos, simplemente podemos evaluar el polinomio cromático correspondiente; Algunos ejemplos en Mathworld .

Supongo que la mayoría de lo anterior es de conocimiento común. Con mucho gusto aprendería si hay otras familias de gráficos (no triviales) para las cuales el color mínimo del gráfico se pueda resolver en tiempo polinómico.

En particular, estoy interesado en algoritmos exactos y deterministas, pero no dude en señalar cualquier algoritmo aleatorio interesante o algoritmo de aproximación.

Actualización (31 de agosto):

Gracias a todos por enviar respuestas interesantes. Aquí hay un breve resumen de las respuestas y referencias.

Gráficos perfectos y casi perfectos.

• Algoritmos geométricos y optimización combinatoria (1988), Capítulo 9 (Conjuntos estables en gráficos). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.

  El Capítulo 9 del libro muestra cómo resolver el problema de coloración a través del problema de cobertura de la camarilla ponderada mínima. Dado que dependen del método elipsoide, estos algoritmos pueden no ser muy útiles en la práctica. Además, el capítulo tiene una buena lista de referencias para diferentes clases de gráficos perfectos.

• Optimización combinatoria (2003), Volumen B, Sección VI Alexander Schrijver.

  Este libro tiene tres capítulos dedicados a gráficos perfectos y su capacidad de coloración polinómica en el tiempo. Solo eché un vistazo rápido, pero el enfoque básico parece el mismo que en el libro anterior.

• Una caracterización de gráficos b-perfectos (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Gráficos con ancho de árbol acotado o ancho de camarilla

• Conjunto y colores dominantes de bordes en gráficos con ancho de camarilla fijo (2001). Daniel Kobler, Udi Rotics

  Los algoritmos aquí requieren una expresión k (una fórmula algebraica para construir un gráfico con un ancho de camarilla acotado) como parámetro. Para algunos gráficos, esta expresión se puede calcular en tiempo lineal.

• Yaroslav señaló en los métodos para contar los colores en los gráficos acotados de ancho de árbol. Ver su respuesta a continuación.

Estas dos familias de gráficos de estudio donde se pueden agregar o eliminar vértices o bordes.$k$

• Complejidad parametrizada de la coloración de vértices (2003). Leizhen Cai.

  La coloración se puede resolver en tiempo polinómico al agregar o eliminar bordes (para k fijo ) en gráficos divididos .$k$$k$

• Problemas de coloración parametrizados en gráficos cordales (2006). Dániel Marx.

  $k$$k$

Gráficos que no contienen subgrafos particulares

• Decidir la k-colorabilidad de los gráficos libres de P5 en el tiempo polinómico (2010). Chính T. Hoàng, Marcin Kamínski, Vadim Lozin, Joe Sawada, Xiao Shu.

• Gráficos de 3 colores sin AT en tiempo polinómico (2010). Juraj Stacho.

Colorear cuadrúteros

• Algoritmos para colorear quadtrees (1999). David Eppstein, Marshall W. Bern, Brad Hutchings.

Como puede observar, todos los gráficos perfectos pueden colorearse en tiempo polinómico, pero creo que la prueba involucra algoritmos elipsoides para programación lineal (vea el libro de Grötschel, Lovász y Schrijver) en lugar de cualquier cosa directa y combinatoria. Hay muchas clases diferentes de gráficos que son subclases de gráficos perfectos y tienen algoritmos de coloración más fáciles; Los gráficos cordales, por ejemplo, pueden colorearse con avidez utilizando un orden de eliminación perfecto.

Todos los gráficos conectados localmente (gráficos en los que cada vértice tiene un vecindario conectado) pueden tener 3 colores en tiempo polinómico, cuando existe un color: simplemente extienda el triángulo de color por triángulo.

Los gráficos de grado máximo tres se pueden colorear en tiempo polinómico: es fácil probar si son bipartitos, y si no, requieren solo tres colores o tienen K4 como componente conectado y requieren cuatro colores (teorema de Brooks).

Las gráficas planas sin triángulos se pueden colorear en tiempo polinómico, por la misma razón: son como máximo 3 cromáticas (teorema de Grötzsch).

Los gráficos b-perfectos permiten 5 ciclos inducidos (a diferencia de los gráficos perfectos), y se demostró que tenían un algoritmo de tiempo polinómico para colorear por Hoàng, Maffray y Mechebbek, caracterización A de gráficos b-perfectos , arXiv: 1004.5306 , 2010.

(Es una pena que el maravilloso compendio de clases de gráficos en el ISGCI solo cubra el ancho de camarilla, el conjunto independiente y la dominación. No incluye información sobre el color).

También para gráficos de ancho de camarilla acotado (que es más general que el ancho de árbol): Kobler y Rotics .

$n^{f(k)}$

Además, el ancho de la camarilla es difícil de calcular, pero hay un algoritmo de aproximación de Oum y Seymour, "aproximando el ancho de la camarilla y el ancho de la rama" (con aproximación exponencial).

$k$

Cualquier familia de gráficos con ancho de árbol acotado tendrá un algoritmo de tiempo polinómico para calcular el número cromático. Gamarnik reduce el problema del recuento de coloraciones al cálculo de los márgenes de ciertos campos aleatorios de Markov definidos en el mismo gráfico. El resultado se debe a que los márgenes de MRF en gráficos de ancho de árbol acotado pueden calcularse en tiempo polinómico con el algoritmo de árbol de unión .

Actualización 8/26 : Aquí hay un ejemplo de "# de colorantes" <-> reducción de márgenes . Requiere comenzar con una coloración adecuada, que se puede encontrar en tiempo polinomial para gráficos de ancho de árbol acotado con la versión max-plus del algoritmo de árbol de unión. Ahora que lo pienso ... realmente no necesita # de colores para el número cromático, solo un color apropiado

$P_5$$C_5$$P_5$

$2P_3$

También hay resultados de Daniel Marx con respecto a la complejidad del problema del número cromático en los gráficos que se pueden hacer cordal a lo sumo k eliminaciones de vértices; para cada k fijo, este problema es polinómico ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Algoritmos para colorear quadtrees .
M. Bern, D. Eppstein y B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87-94, 2002.

Consideramos varias variaciones del problema de colorear los cuadrados de un quadtree para que no haya dos cuadrados adyacentes iguales. Proporcionamos algoritmos de tiempo lineal simples para cuadrúculos balanceados de 3 colores con adyacencia de borde, cuadrúculos no balanceados de 4 colores con adyacencia de borde y cuadrúculos balanceados o no balanceados de 6 colores con adyacencia de esquina. El número de colores utilizados por los dos primeros algoritmos es óptimo; para el tercer algoritmo, a veces pueden ser necesarios 5 colores.