Superlinear CZ-distance for circle graphs

About 1 year old · traced to

Let GG be an nn-vertex circle graph, and let CZ⁡(G)\operatorname{CZ}(G) denote its CZ-distance. Circle-graph lower-bound conjecture. There exist nn-vertex circle graphs GG with

CZ⁡(G)=Ω(nlog⁡n).\operatorname{CZ}(G)=\Omega(n\log n).

The conjecture would close the remaining logarithmic gap between the paper's O(nlog⁡n)O(n\log n) upper bound for circle graphs and the general linear lower bound; the source gives no resolution.

References

Primary source

James Davies and Andrew Jena, “Preparing graph states forbidding a vertex-minor”, arXiv:2504.00291 (2025).

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.