Improved Upper Bounds on Color Reversal by Local Inversions
摘要
We study the problem of color reversal in bicolored graphs under local inversions. A bicoloration of a graph \(G=(V,E)\) is a mapping \(\beta : V \rightarrow \{-1,1\}\) . A local inversion at a vertex \(v \in V\) consists of reversing the colors of all neighbors of v and replacing the subgraph induced by these neighbors with its complement, while leaving v and the rest of G unchanged. Sabidussi (Discrete Mathematics, 1987) showed that any bicolored graph on n vertices without isolated vertices can be color-reversed (that is, all vertex colors flipped while preserving the underlying graph) in at most \(6n+3\) local inversions, and that any bicolored graph can be transformed into another bicolored graph on the same underlying graph in at most 9n local inversions. We improve both bounds: we prove that the first task can be accomplished in at most \(4n-3\) local inversions, and the second in at most \( \left\lfloor \frac{11n-3}{2} \right\rfloor \) local inversions. Furthermore, we show that for stars and complete graphs, color reversal can be performed with at most 3n local inversions.