The bipartisan graph quasi-parity conjecture

A bipartisan graph is a graph such that neither it nor its complement has an odd hole, a long prism, a double-diamond, or L(K3,3e)L(K_{3,3}\setminus e). A quasi-parity graph is a graph in which every induced subgraph or its complement has an even pair.

Maffray–Thomas conjecture. Every bipartisan graph is a quasi-parity graph.

The conjecture was proposed as a possible replacement for the final part of the proof of the strong perfect graph theorem for bipartisan graphs. The supplied status evidence says that this claim is false.

Sources & referencesView supporting material

Primary source

Michel Burlet, Frédéric Maffray and Nicolas Trotignon, “Odd pairs of cliques”, arXiv:1309.0449 (2013).

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.