Partition of graphs with maximum degree ratio

Valentin Bouquet, François Delbot, Christophe Picouleau

Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V…