The alternating-circuit bound for balanced red-blue graphs
Let be a balanced red-blue graph with vertices and edges. An alternating-circuit bound asserts that
- there exists an alternating circuit of length at most ; and
- .
Such an upper bound would provide a lower bound on the swap-distance and could therefore be useful in practical applications.
References
- Péter L. Erdős, Zoltán Király and István Miklós, “On the swap-distances of different realizations of a graphical degree sequence”, arXiv:1205.2842 (2013).
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.