Bowler–Brown–Fenner common-card bound for trees and connected non-trees

Let GG and HH be graphs on nn vertices, where one is a tree and the other is a connected non-tree. A common card is an unlabeled graph occurring as a card in the decks of both GG and HH. Bowler–Brown–Fenner conjecture. For n44n\geq 44, the only pair of graphs on nn vertices having at least 25(n+1)\lfloor \frac{2}{5}(n+1)\rfloor common cards is the pair found in Theorem 3.6 of Bowler, Brown, and Fenner. This conjecture concerns the extremal overlap between the decks of trees and connected non-trees; 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.