Arising from the VLSI design and network communication, the cutwidth problem for a graph \(G\) is to embed \(G\) into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The characterization of forbidden subgraphs or critical graphs is meaningful in the study of a graph-theoretic parameter. This paper characterizes the set of \(4\)-cutwidth critical trees by twelve specified ones.
Citation
Zhenkun Zhang, Yixun Lin. On \(4\)-Cutwidth Critical Trees[J], Ars Combinatoria, Volume 105. 149-160. .