Maximum-average-degree conjecture for non-2-mixing oriented graphs

About 7 years old · traced to

Let an oriented graph be a digraph with no pair of oppositely directed parallel arcs, and let its maximum average degree be the maximum of 2∣A(H)∣/∣V(H)∣2|A(H)|/|V(H)| over all non-empty subdigraphs HH. A digraph is 2-mixing if any two of its 2-dicolourings can be connected by single-vertex recolourings through 2-dicolourings. Oriented-graph density conjecture. Every non-2-mixing oriented graph has maximum average degree at least 44. This is supported in the paper by proving the claim for 2-freezable oriented graphs; the general conjecture remains open.

References

Primary source

Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta and Amadeus Reinald, “Digraph redicolouring”, arXiv:2301.03417 (2023).

Additional references

2 papers in this index state this conjecture (2019–2023). The statement above is taken from the most recent of them; the others are arXiv:1911.02672.

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.