Deletion–triangle subdivision conjecture for Hilbert bases of cuts

About 12 years old · traced to

Let GG be a graph in the class H\mathscr{H} of graphs whose cut semigroup has the Hilbert basis property, and let f∈E(G)f\in E(G) be an edge. Write G∖fG\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

G∖f∈Hif and only ifG+fC3∈H.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 n≥4n\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.

References

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.