Geelen–Gerards–Whittle polynomial-time girth conjecture for proper minor-closed classes
Geelen–Gerards–Whittle polynomial-time girth conjecture for proper minor-closed classes
Let 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 . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.