Maximum-average-degree conjecture for non-2-mixing oriented graphs
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 over all non-empty subdigraphs . 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 . 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
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.