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 GG is uniquely decomposable by a balanced skew partition, then one of GG or G\overline{G} 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

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.