← All problems

The alternating-circuit bound for balanced red-blue graphs

14 years old · traced to

Let GG be a balanced red-blue graph with nn vertices and mm edges. An alternating-circuit bound asserts that

  1. there exists an alternating circuit of length at most 3n2/m3n^2/m; and
  2. maxCu(G)≥m2/(6n2)\mathbf{maxC}_u(G)\ge m^2/(6n^2).

Such an upper bound would provide a lower bound on the swap-distance and could therefore be useful in practical applications.

References
  1. 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.