An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem

Min Chih Lin, Natán Vekselman

For a fixed integer $r\ge 4$, the $K_r-e$-free graph sandwich problem asks whether, given graphs $G_1\subseteq G_2$ on the same vertex set, there is an induced-$K_r-e$-free graph $…