The finite-colour Seurat game conjecture for digraphs
The finite-colour Seurat game conjecture for digraphs
Let be the Seurat game with colours played on digraphs and , with players and , where seeks to distinguish non-isomorphic digraphs and seeks to match the colouring moves. Seurat game conjecture. There is such that for all digraphs , if then has a winning strategy in
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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.