Conjecture on polynomial-time enumeration of regular graphs

Fix kgreaterthanorequalto1k greater than or equal to 1 and let ana_n be the number of unlabeled kk-regular graphs with nn vertices.

Regular-graph enumeration conjecture. The sequence ana_n can be computed in polynomial time in nn.

The source notes polynomial recurrences for labeled kk-regular graphs for each fixed kk, 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

No solutions have been posted yet.