Załóżmy, że jest wykresem z liczbą barwiącą d = χ ( G ) . Rozważ następującą grę między Alicją i Bobem. W każdej rundzie Alicja wybiera wierzchołek, a Bob odpowiada kolorem { 1 , … , d - 1 } dla tego wierzchołka. Gra kończy się, gdy zostanie odkryta monochromatyczna krawędź. Niech X ( G ) 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 X ( K n ) = ni .
Czy ta gra jest znana?
4
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ę X ( G ) . W aplikacji, o której myślę, k ≥ χ ( G ) nie ma sensu.
—
Yuval Filmus
@Tyson: W rzeczywistości jest złożonością drzewa decyzyjnego w grze, w której, biorąc pod uwagę kolorystykę d - 1 G , chcemy znaleźć naruszoną krawędź.
—
Yuval Filmus