Complexidade de coloração de gráficos

27

Suponha que é um gráfico com o número de coloração d = χ ( G ) . Considere o seguinte jogo entre Alice e Bob. Em cada rodada, Alice escolhe um vértice e Bob responde com uma cor em { 1 , , d - 1 } para esse vértice. O jogo termina quando uma borda monocromática é descoberta. Seja X ( G ) a duração máxima do jogo em jogo ideal por ambos os jogadores (Alice deseja encurtar o jogo o máximo possível, Bob quer adiá-lo o máximo possível). Por exemplo, X ( K n ) = nGd=χ(G){1,,d1}X(G)X(Kn)=ne .X(C2n+1)=Θ(logn)

Este jogo é conhecido?

Yuval Filmus
fonte
4
Acho que você pode modelar isso como um jogo de Ehrenfeucht-Fraïssé .
Tyson Williams
1
parece estar altamente relacionado a algoritmos gananciosos de coloração de gráficos, certo? dos quais existem muitos .... da mesma forma que os problemas do SAT, em que uma das variáveis ​​é "forçada" após alguma passagem da DPLL ... que eu acredito que também é chamada de "espinha dorsal" no SAT
vzn
2
Por que você usa d-1? Penso que é mais natural parametrizar o jogo pelo gráfico G e pelo número k de cores permitidas e considerar a quantidade análoga X (G, k). Obviamente, se k≥χ (G), Bob vence e, portanto, neste caso, X (G, k) deve ser definido como ∞ ou n + 1.
Tsuyoshi Ito
1
@ Tsuyoshi: é uma escolha arbitrária projetada para maximizar X ( G ) . Na aplicação que tenho em mente, k χ ( G ) não faz sentido. k=d1X(G)kχ(G)
Yuval Filmus
@ Tyson: De fato, é a complexidade da árvore de decisão do jogo em que, dada uma coloração d - 1 de G , queremos encontrar uma vantagem violada. X(G)d1G
Yuval Filmus

Respostas:

11

Parece bastante semelhante a

Colorir online gráficos aleatórios sem criar subgráficos monocromáticos (Reto Spöhel, Torsten Mütze e Thomas Rast) Anais do 22º Simpósio Anual ACM-SIAM sobre Algoritmos Discretos (SODA '11), PR 137, 145-158.

adrianN
fonte