Everett–Reed's conjecture on even-contractile Berge graphs
Everett–Reed's conjecture on even-contractile Berge graphs
Let 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 has no induced subgraph isomorphic to an antihole of length at least six or to an odd prism, then 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
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.