Common-card bound for bipartite and non-bipartite graphs

Let GG be a bipartite graph and HH a non-bipartite graph, both on nn vertices. A common card is an unlabeled vertex-deleted subgraph occurring in the decks of both graphs. Bipartiteness conjecture. For nn large enough, the number of common cards between GG and HH is at most n2+1\lfloor \frac{n}{2}\rfloor+1. The conjecture proposes the expected sharp lower bound on the number of cards needed to distinguish bipartite from non-bipartite graphs; the source does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Gabriëlle Zwaneveld, “Recognizing trees from incomplete decks”, arXiv:2311.16665 (2023).

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.