Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.00149 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915527409008640 |
|---|---|
| author | Porte, Kumud Singh Sandeep, RB Santra, Kamal |
| author_facet | Porte, Kumud Singh Sandeep, RB Santra, Kamal |
| contents | We study the problem of color reversal in bicolored graphs under local inversions. A \emph{bicoloration} of a graph $G=(V,E)$ is a mapping $β: V \to \{-1,1\}$. A \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00149 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved upper bounds on color reversal by local inversions Porte, Kumud Singh Sandeep, RB Santra, Kamal Combinatorics We study the problem of color reversal in bicolored graphs under local inversions. A \emph{bicoloration} of a graph $G=(V,E)$ is a mapping $β: V \to \{-1,1\}$. A \emph{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. |
| title | Improved upper bounds on color reversal by local inversions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.00149 |