Kolorystyka złożoności wykresów

Załóżmy, że jest wykresem z liczbą barwiącą . Rozważ następującą grę między Alicją i Bobem. W każdej rundzie Alicja wybiera wierzchołek, a Bob odpowiada kolorem dla tego wierzchołka. Gra kończy się, gdy zostanie odkryta monochromatyczna krawędź. Niech będzie maksymalną długością gry przy optymalnej grze przez obu graczy (Alice chce skrócić grę, jak to możliwe, Bob chce ją jak najszybciej opóźnić). Na przykład $G$ $d = \chi(G)$ $\{1,\ldots,d-1\}$ $X(G)$ $X(K_n) = n$ i . $X(C_{2n+1}) = \Theta(\log n)$

Czy ta gra jest znana?

reference-request graph-theory co.combinatorics graph-colouring decision-trees Yuval Filmus
źródło

Myślę, że możesz to wymodelować jako grę Ehrenfeucht – Fraïssé .

Tyson Williams

wydaje się, że jest bardzo związany z chciwymi algorytmami kolorowania grafów, prawda? z których istnieje wiele ... podobnie jak problemy SAT, w których jedna ze zmiennych jest "wymuszona" po pewnym przejściu DPLL ... które, jak sądzę, jest również nazywane "szkieletem" w SAT

vzn

Dlaczego używasz d-1? Myślę, że bardziej naturalne jest sparametryzowanie gry zarówno na podstawie wykresu G, jak i liczby k dozwolonych kolorów i rozważenie analogicznej wielkości X (G, k). Oczywiście, jeśli k≥χ (G), wtedy Bob wygrywa, a zatem w tym przypadku X (G, k) należy zdefiniować jako ∞ lub n + 1.

Tsuyoshi Ito

@Tsuyoshi:

to dowolny wybór mający na celu maksymalizację

. W aplikacji, o której myślę,

nie ma sensu.

k = d - 1

$k = d-1$

X (G)

$X(G)$

k \geq χ (G)

$k \geq \chi(G)$

Yuval Filmus

@Tyson: W rzeczywistości

jest złożonością drzewa decyzyjnego w grze, w której, biorąc pod uwagę kolorystykę

, chcemy znaleźć naruszoną krawędź.

X (G)

$X(G)$

d - 1

$d-1$

G

$G$

Yuval Filmus

Kolorystyka złożoności wykresów

Odpowiedzi: