Conjecture on polynomial-time enumeration of regular graphs

About 8 years old · traced to

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.

References

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.