Improved Lower Bounds for the Cyclic Bandwidth Problem

We study the classical Cyclic Bandwidth problem, an optimization problem which takes as input an undirected graph \(G=(V,E)\) with \(|V|=n\), and asks for a labeling \(\varphi \) of V in which every vertex v takes a unique value \(\varphi (v)\in [1;n]\), in such a way that \(B_c(G,\varphi )=\max \{\min _{uv\in E(G)}\{|\varphi (u)-\varphi (v)|,n-|\varphi (u)-\varphi (v)|\}\}\), called the cyclic bandwidth of G, is minimized.