The ordered-forest core conjecture for polynomial testability
Let be an ordered graph, meaning a graph equipped with a linear order on its vertices. An ordered forest is an ordered graph whose underlying graph is a forest, and the core of is its smallest retract under order-preserving graph homomorphisms. Let denote the query complexity of testing -freeness. Ordered-forest core conjecture.
The conjecture was posed by the first author and Tomon. It seeks a characterization of polynomial testability for ordered graph properties; the source states that it remains open.
References
Primary source
Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).
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
No solutions have been posted yet.