Abstract:
We propose a universal approach to a range of enumeration problems in graphs by means of tensor networks. The key point is in contracting suitably chosen symmetric tensors placed at the vertices of a graph along the edges. This approach leads to simple formulas that count, in particular, the number of $d$-regular subgraphs of an arbitrary graph (including the number of $d$-factors) and proper edge colorings. We briefly discuss the problem of the computational complexity of the algorithms based on these formulas.
Key words and phrases:tensor network, $d$-regular subgraph, $d$-factor, edge coloring.