Universal graph for graphs with cutwidth at most 2

Abstract

A graph {\it has cutwidth at most 2} if one can number its vertices by $1,\dots n$ so that for every $i=1,\dots ,n-1$ there are at most 2 edges $(u,v)$ such that $u\le i<v$. A characterization of graphs having cutwidth at most 2 in terms of prohibited subgraphs was obtained by Y. Lin, A. Yang. We present an alternative characterization of such graphs in terms of universal graph.

in Russian