Burr's universality conjecture for oriented trees

About 10 years old · traced to

Let nn be a positive integer. An oriented tree is an orientation of a tree. A digraph is nn-universal if it is contained in every nn-chromatic digraph.

Burr's conjecture. Every oriented tree of order nn is (2n−2)(2n-2)-universal.

This is a generalization of Sumner's conjecture, which asserts that every oriented tree of order nn is contained in every tournament of order 2n−22n-2. The supplied text gives no evidence resolving Burr's stronger universality conjecture.

References

Primary source

Batoul Tarhini, “About the existence of oriented paths with three blocks”, arXiv:2312.09905 (2023).

Additional references

8 papers in this index state this conjecture (2016–2023). The statement above is taken from the most recent of them; the others are arXiv:2310.18719, arXiv:2010.10787, arXiv:1912.04004, arXiv:1812.05167, arXiv:1703.02230, arXiv:1610.00876, arXiv:1605.07762.

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.