Geelen–Gerards–Whittle polynomial-time girth conjecture for proper minor-closed classes

Let M\mathcal{M} be a proper minor-closed class of binary matroids. Geelen–Gerards–Whittle's conjecture. There is a polynomial-time algorithm for computing the girth of matroids in M\mathcal{M}. This conjecture connects the tractability of girth computation with structural restrictions on binary matroid classes; the paper studies an algorithmic result for perturbed graphic matroids, while the conjecture concerns every proper minor-closed class of binary matroids.

Sources & referencesView supporting material

Primary source

Jim Geelen and Rohan Kapadia, “Computing girth and cogirth in perturbed graphic matroids”, arXiv:1504.07647 (2015).

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.