Complejidad de coloración de gráficos

27

Supongamos que es un gráfico con el número de colorante . Considere el siguiente juego entre Alice y Bob. En cada ronda, Alice elige un vértice y Bob responde con un color en para este vértice. El juego termina cuando se descubre un borde monocromático. Deje que sea ​​la duración máxima del juego bajo el juego óptimo de ambos jugadores (Alice quiere acortar el juego lo más posible, Bob quiere retrasarlo lo más posible). Por ejemplo, y .Gd=χ(G){1,,d1}X(G)X(Kn)=nX(do2norte+1)=Θ(Iniciar sesiónnorte)

¿Se conoce este juego?

Yuval Filmus
fuente
44
Creo que puedes modelar esto como un juego Ehrenfeucht – Fraïssé .
Tyson Williams
1
parece estar muy relacionado con los algoritmos de coloración de gráficos codiciosos, ¿verdad? de los cuales hay muchos ... de manera similar a los problemas de SAT donde una de las variables es "forzada" después de un recorrido DPLL ... que creo que también se llama la "columna vertebral" en SAT
vzn
2
¿Por qué usas d − 1? Creo que es más natural parametrizar el juego tanto por el gráfico G como por el número k de colores permitidos y considerar la cantidad análoga X (G, k). Por supuesto, si k≥χ (G), entonces Bob gana, y por lo tanto, en este caso, X (G, k) debe definirse como ∞ o n + 1.
Tsuyoshi Ito
1
@ Tsuyoshi: es una elección arbitraria diseñada para maximizar . En la aplicación que tengo en mente, no tiene sentido. X ( G ) k χ ( G )k=re-1X(sol)kχ(sol)
Yuval Filmus
@Tyson: De hecho, es la complejidad del árbol de decisiones del juego en el que, dada una coloración de , queremos encontrar un borde violado. d - 1 GX(sol)re-1sol
Yuval Filmus

Respuestas:

11

Se ve bastante similar a

Colorear gráficos aleatorios en línea sin crear subgrafías monocromáticas (Reto Spöhel, Torsten Mütze y Thomas Rast) Actas del 22º Simposio anual ACM-SIAM sobre Algoritmos discretos (SODA '11), PR 137, 145-158.

adrianN
fuente