The ordered-forest core conjecture for polynomial testability
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.