Everett–Reed's conjecture on even-contractile Berge graphs

Let GG be a Berge graph, meaning a graph with no induced odd hole and no induced odd antihole. An antihole is the complement of a hole, and an odd prism is a prism whose three rungs all have an odd number of edges. A graph is even-contractile if it can be reduced to a single vertex by contracting edges whose endpoints have no common neighbor. Everett–Reed's conjecture. If GG has no induced subgraph isomorphic to an antihole of length at least six or to an odd prism, then GG is even-contractile. This conjecture concerns a proposed characterization of even-contractile Berge graphs and remains open, although several related theorems have been proved.

Sources & referencesView supporting material

Primary source

Tara Abrishami, Maria Chudnovsky and Yaqian Tang, “Even pairs in Berge graphs with no balanced skew-partitions”, arXiv:2305.00532 (2024).

Additional references

6 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:2303.12824, arXiv:1502.03695, arXiv:1309.0435, arXiv:1309.0438, arXiv:1301.5149.

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.