Strong SDP based bounds on the cutwidth of a graph

Elisabeth Gaar, Diane Puges, Angelika Wiegele

Given a linear ordering of the vertices of a graph, the cutwidth of a vertex $v$ with respect to this ordering is the number of edges from any vertex before $v$ (including $v$) to…