Thomas's balanced-skew-partition even-pair conjecture
Thomas's balanced-skew-partition even-pair conjecture
A graph is Berge if it has no odd hole and no odd antihole. A balanced skew partition is the balanced form of a skew partition used in the decomposition theory of Berge graphs. A graph is uniquely decomposable by a balanced skew partition when it is not basic, has no 2-join, and has no complement 2-join. An even pair is a pair of vertices such that every chordless path between them has even length. Thomas's conjecture. If a Berge graph is uniquely decomposable by a balanced skew partition, then one of or has an even pair. The conjecture is motivated by the difficulty of obtaining polynomial colouring algorithms for Berge graphs with balanced skew partitions. The survey describes it as unpublished and does not report a resolution.
Sources & referencesView supporting material
Primary source
Nicolas Trotignon, “Perfect graphs: a survey”, arXiv:1301.5149 (2015).
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.