Conjecture on polynomial-time enumeration of regular graphs
Conjecture on polynomial-time enumeration of regular graphs
Fix and let be the number of unlabeled -regular graphs with vertices.
Regular-graph enumeration conjecture. The sequence can be computed in polynomial time in .
The source notes polynomial recurrences for labeled -regular graphs for each fixed , but does not establish the corresponding claim for unlabeled graphs. No resolution is supplied.
Sources & referencesView supporting material
Primary source
Igor Pak, “Complexity problems in enumerative combinatorics”, arXiv:1803.06636 (2018).
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
Sign in to submit a solution.
No solutions have been posted yet.