Existence of extremal graphs for every degeneracy
Existence of extremal graphs for every degeneracy
Let be an integer with . A graph is -degenerate if every subgraph has a vertex of degree at most . Let denote the subgraph query complexity, and write for the relevant query parameter.
Extremal graph existence conjecture. For every integer , there exists a -degenerate graph such that
In the case , the paper constructs such a graph, whereas the existence of such graphs for remains open.
Sources & referencesView supporting material
Primary source
Ryan Alweiss, Chady Ben Hamida, Xiaoyu He and Alexander Moreira, “On the subgraph query problem”, arXiv:1911.04413 (2020).
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.