Decomposability of a class of k-cutwidth critical graphs

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line $$P_n$$ with $$n=|V(G)|$$ vertices, in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we mainly investigated a class of decomposable k-cutwidth critical graphs for $$k\ge 2$$ , which can be decomposed into three $$(k-1)$$ -cutwidth critical subgraphs.