Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width

Matthias Lanzinger, Timo Camillo Merkl, Dan Suciu

We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, e…