The bipartisan graph quasi-parity conjecture
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 . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.