Maffray's bipartisan even-pair conjecture

About 13 years old · traced to

A graph is bipartisan if it is Berge, contains no L(K3,3∖e)L(K_{3,3}\setminus e) and no double diamond, and neither GG nor G‾\overline{G} contains a long prism. An even pair is a pair of vertices such that every chordless path between them has even length. Maffray's conjecture. If GG is bipartisan with at least two vertices, then at least one of GG and G‾\overline{G} contains an even pair. This would generalize the bull-free Berge graph theorem and could shorten the proof of the strong perfect graph theorem. The survey presents it as an open conjecture.

References

Primary source

Nicolas Trotignon, “Perfect graphs: a survey”, arXiv:1301.5149 (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.