Carvalho–Lucchesi–Murty laminar ELP cut conjecture

Let GG be a matching covered graph, and let CC be a nontrivial tight cut of GG. An ELP cut is a barrier-cut or a 2-separation cut.

Carvalho–Lucchesi–Murty conjecture. The graph GG has a nontrivial ELP cut that is laminar with CC.

If true, this would imply that every nontrivial tight cut of GG is ultimately an ELP cut in an ELP cut decomposition. The statement is presented as a conjecture in the source; its resolution is not established by the supplied text.

Sources & referencesView supporting material

Primary source

Guantao Chen, Xing Feng, Fuliang Lu, Cláudio L. Lucchesi and Lianzhu Zhang, “Laminar Tight Cuts in Matching Covered Graphs”, arXiv:2003.08622 (2020).

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.