The retract characterization conjecture for hypercellular graphs

Let GG be a partial cube. A retract of a graph HH is a subgraph admitting a graph homomorphism from HH to the subgraph that restricts to the identity on the subgraph. A Cartesian product of graphs is formed by taking vertex tuples and joining tuples that differ in exactly one coordinate along an edge in that factor. Bipartite cellular graphs are the class used in the paper.

The retract characterization conjecture. A partial cube GG is hypercellular if and only if GG is a retract of a Cartesian product of bipartite cellular graphs.

This is proposed as an analogue of the fact that median graphs are precisely retracts of hypercubes. The supplied text gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Victor Chepoi, Kolja Knauer and Tilen Marc, “Hypercellular graphs: partial cubes without Q_3^- as partial cube minor”, arXiv:1606.02154 (2019).

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.