Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs

Akash Kumar, Abhiruk Lahiri, C. Seshadhri

Consider a bounded-degree graph $G$ that belongs to a minor-closed family (such as planar graphs). Such a graph has a hyperfinite decomposition, wherein, for a sufficiently small $…