On the Complexity of Counting Orderings in Graphs

Marcelo Arenas, María Alejandra Schild, Bernardo Subercaseaux

We study the computational complexity of several counting problems on graphs. Each of these problems consists of counting orderings of the vertices or edges with adjacency constrai…