The O(G)O(G) conjecture on minimal synchronizing factors

Let GG be a strongly connected graph. Write H\foldSGH\fold_S G when HH is a synchronizing factor of GG, and let O(G)O(G) denote a candidate minimal synchronizing factor.

O(G)O(G) conjecture. The set of graphs HH with H\foldSGH\fold_S G has a unique \foldS\fold_S-minimal element O(G)O(G).

This conjecture asserts that every strongly connected graph has a well-defined canonical minimal synchronizing factor. It is known in several classes, including graphs related to the road-colouring theorem and almost bunchy graphs, but is open in general.

Sources & referencesView supporting material

Primary source

Sophie MacDonald, “The road problem and homomorphisms of directed graphs”, arXiv:2201.12942 (2023).

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.