Deletion–triangle subdivision conjecture for Hilbert bases of cuts

Let GG be a graph in the class H\mathscr{H} of graphs whose cut semigroup has the Hilbert basis property, and let fE(G)f\in E(G) be an edge. Write GfG\setminus f for deletion of ff, and G+fC3G+_f C_3 for the graph obtained by replacing ff with a triangle. Deletion–triangle subdivision conjecture. Then

GfHif and only ifG+fC3H.G\setminus f\in\mathscr{H}\quad\text{if and only if}\quad G+_f C_3\in\mathscr{H}.

The preceding theorem establishes the analogous equivalence with CnC_n for every n4n\geq 4; the case of subdivision by a triangle is left as a conjecture because one direction of that proof breaks down when the edge is subdivided only once.

Sources & referencesView supporting material

Primary source

Luis Goddyn, Tony Huynh and Tanmay Deshpande, “On Hilbert bases of cuts”, arXiv:1409.5451 (2014).

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.