Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

Balagopal Komarath, Rohit Narayanan

We introduce baggy elimination trees, a novel graph decomposition that generalises the classical elimination trees underlying treedepth, and use them to give a complete characteris…