The retract characterization conjecture for hypercellular graphs
The retract characterization conjecture for hypercellular graphs
Let be a partial cube. A retract of a graph is a subgraph admitting a graph homomorphism from 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 is hypercellular if and only if 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
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.