The dijoin conjecture for oriented graphs

At least 3 years old · documented by

Let LL) and RR be oriented graphs. Their dijoin L→RL\rightarrow R is formed from vertex-disjoint copies of LL and RR, with every edge directed from LL to RR.

Dijoin conjecture.

inv⁡(L→R)=inv⁡(L)+inv⁡(R).\operatorname{inv}(L\rightarrow R)=\operatorname{inv}(L)+\operatorname{inv}(R).

This conjecture is refuted in the paper by a counterexample, although it holds in several special cases.

References

Primary source

Noga Alon, Emil Powierski, Michael Savery, Alex Scott and Elizabeth Wilmer, “Invertibility of digraphs and tournaments”, arXiv:2212.11969 (2024).

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.