Minor-closed-family conjecture for oriented chromatic number

About 18 years old · traced to

For a minor-closed family of graphs G\mathcal{G}, let ωo(G)\omega_o(\mathcal{G}) be the order of a largest oriented clique in G\mathcal{G}.

Minor-closed-family conjecture. There exists a function f:N→Nf:\mathbb{N}\rightarrow\mathbb{N} such that f(n)=n1+o(1)f(n)=n^{1+o(1)} and, for every minor-closed family of graphs G\mathcal{G},

max⁡G∈Gχo⁡(G)≤f(ωo(G)).\max_{G\in\mathcal{G}} \operatorname{\chi_o}(G) \leq f(\omega_o(\mathcal{G})).

The conjecture proposes that, across every minor-closed graph family, the maximum oriented chromatic number is at most a nearly linear function of the largest oriented clique order. The paper presents this as a possible general pattern motivated by the bounds for graphs on surfaces.

References

Primary source

Alexander Clow, “On Oriented Colourings of Graphs on Surfaces”, arXiv:2409.13076 (2024).

Additional references

3 papers in this index state this conjecture (2008–2024). The statement above is taken from the most recent of them; the others are arXiv:1301.5271, arXiv:0804.1573.

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.