The edge-deletion conjecture for upper thresholds
The edge-deletion conjecture for upper thresholds
Let be a graph with at least three edges. For an edge of , let be the graph obtained by deleting , together with a vertex of degree one if that vertex is an endpoint of . Let and denote the upper and lower thresholds of the strict Avoider–Enforcer games. Edge-deletion conjecture. For every graph with at least three edges, one has
The conjecture proposes that the upper threshold is governed by the largest lower threshold among the edge-deleted graphs; the source presents it as an open problem for general graphs.
Sources & referencesView supporting material
Primary source
Małgorzata Bednarska-Bzdȩga, Omri Ben-Eliezer, Lior Gishboliner and Tuan Tran, “On the separation conjecture in Avoider-Enforcer games”, arXiv:1709.09065 (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.