The finite-colour Seurat game conjecture for digraphs

Let Gn(G,H){\bf G}^n(G,H) be the Seurat game with nn colours played on digraphs GG and HH, with players \forall and \exists, where \forall seeks to distinguish non-isomorphic digraphs and \exists seeks to match the colouring moves. Seurat game conjecture. There is n2n\geq 2 such that for all digraphs G,HG,H, if G≇HG\not\cong H then \forall has a winning strategy in

Gn(G,H).{\bf G}^n(G,H).

If true, this would say that a fixed finite number of colours suffices to distinguish every pair of non-isomorphic digraphs in these games; the source describes the question as open and notes that no pair of non-isomorphic graphs is known on which \exists can avoid losing even with two colours.

Sources & referencesView supporting material

Primary source

Rob Egrot and Robin Hirsch, “Seurat games on Stockmeyer graphs”, arXiv:2008.01327 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.