The rotation graph \(\mathcal {R}(G)\) is the graph whose vertices correspond to search trees on a graph G, with edges determined by rotation operations. In this paper, we analyze how the structure of a rotation graph changes when certain operations are applied to the underlying graph G. Specifically, we examine the effects of three key operations: adding a pendant vertex, adding a true twin to a vertex, and adding a false twin to a vertex. For each of these operations, we provide a full structural characterization of the new rotation graph. Using these descriptions, we investigate the chromatic number of rotation graphs, identifying conditions under which this parameter remains unchanged. As an application, we show that the chromatic number of the rotation graphs of non-complete threshold graphs (including complete split graphs and star graphs) and complete bipartite graphs is 3.
