pith. sign in

arxiv: 2606.09066 · v1 · pith:M2CNIBVOnew · submitted 2026-06-08 · 🧮 math.CO

Tight Upper Bounds on Color Reversal by Local Inversions

Hitendra Kumar , Kumud Singh Porte , R. B. Sandeep This is my paper

Pith reviewed 2026-06-27 16:34 UTC · model grok-4.3

classification 🧮 math.CO
keywords bicoloringlocal inversioncolor reversalgraph reconfigurationtight boundcomplete graphstar graphpolynomial-time algorithm
0
0 comments X

The pith

Any two bicolorings of a graph on n vertices without isolated vertices can be transformed into each other using at most 3n local inversions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for graphs without isolated vertices, local inversions suffice to change any bicoloring into any other in at most 3n steps. This improves the prior upper bound of 4n-3 and establishes that the new bound is tight. Tightness follows from showing that complete graphs and stars require at least 3n inversions to reverse every vertex color. The argument supplies an explicit polynomial-time procedure that outputs the required sequence of operations.

Core claim

For every graph on n vertices without isolated vertices, any bicoloring can be transformed into any other bicoloring using at most 3n local inversions. This bound is best possible: for complete graphs and stars on n vertices, at least 3n local inversions are required to reverse the colors of all vertices. The proof is constructive and yields a polynomial-time algorithm that produces the sequence.

What carries the argument

The local inversion at a vertex v, which reverses the colors of all neighbors of v and complements the subgraph induced by those neighbors.

If this is right

  • The diameter of the reconfiguration graph on bicolorings is at most 3n for every such graph.
  • A transforming sequence of length at most 3n can be produced by a polynomial-time algorithm.
  • Complete graphs and stars attain the lower bound of exactly 3n for full color reversal.
  • The earlier bounds of 4n-3 and floor((11n-3)/2) are superseded.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same linear bound may hold for other local operations that flip colors along neighborhoods.
  • Reconfiguration distance questions for bicolorings on graphs with isolates could be settled by treating isolates as fixed points.
  • The polynomial-time construction supplies an efficient method for solving the corresponding search problem in the reconfiguration graph.

Load-bearing premise

The graph has no isolated vertices, since an isolated vertex is unaffected by every local inversion.

What would settle it

A single graph on n vertices with no isolated vertices together with two bicolorings that cannot be transformed into each other by any sequence of 3n or fewer local inversions would falsify the upper bound.

read the original abstract

A bicoloration of a graph $G=(V,E)$ is a map $\beta:V\to\{-1,1\}$. A local inversion at a vertex $v$ complements the subgraph induced by the neighbors of $v$ and simultaneously reverses the colors of all neighbors of $v$. Sabidussi (Discrete Mathematics, 1987) showed that every bicolored graph on $n$ vertices without isolated vertices admits a color reversal using at most $6n+3$ local inversions, and that any two bicolorings of such a graph can be transformed into each other using at most $9n$ local inversions. Recently, Porte, Sandeep, and Santra (CALDAM 2026) improved these bounds to $4n-3$ and $\lfloor(11n-3)/2\rfloor$, respectively. We prove the tight bound $3n$ by showing that, for every graph on $n$ vertices without isolated vertices, any bicoloring can be transformed into any other bicoloring using at most $3n$ local inversions. We also show that this bound is best possible: for complete graphs and stars on $n$ vertices, at least $3n$ local inversions are required to reverse the colors of all vertices. Moreover, the proof of the upper bound is constructive: given two bicolorings, it produces, in polynomial time, a sequence of at most $3n$ local inversions transforming one into the other.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that for any graph G on n vertices with no isolated vertices, any two bicolorings can be transformed into each other using at most 3n local inversions (where a local inversion at v complements the induced subgraph on N(v) and reverses the colors of all neighbors of v). This improves Sabidussi's 9n bound and the recent floor((11n-3)/2) bound. The proof is constructive and yields a polynomial-time algorithm. The bound is shown to be tight because reversing all colors on K_n or on a star requires at least 3n local inversions, established via an invariant (a linear combination of the color vector and an edge-parity vector over GF(2)) that changes by at most 1 per operation.

Significance. The result supplies the first tight 3n bound on the diameter of the reconfiguration graph under this operation, together with an explicit polynomial-time algorithm that realizes the bound. The matching lower bound for two infinite families (complete graphs and stars) is obtained from a simple, parameter-free invariant. These features make the contribution a clear advance over the prior 4n-3 / floor((11n-3)/2) results.

minor comments (2)
  1. The abstract states the upper bound for arbitrary pairs of bicolorings but the lower-bound examples are stated only for the all-reversal target; a single sentence clarifying that the diameter is therefore exactly 3n would help readers.
  2. Section 3 (or wherever the algorithm is presented) should include a brief pseudocode block or numbered steps; the current prose description is correct but makes it harder to verify the claimed O(n) length and polynomial runtime at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; constructive proof with independent invariant

full rationale

The manuscript supplies an explicit constructive algorithm that produces a sequence of at most 3n local inversions between arbitrary bicolorings on any n-vertex graph with minimum degree at least 1. The lower-bound argument for K_n and for stars proceeds by exhibiting an invariant (a linear combination of color vector and edge-parity vector over GF(2)) whose value changes by at most 1 under each local inversion, forcing at least 3n steps for the all-reversal target. Both directions are fully detailed and contain no circularity or hidden assumption on connectivity beyond the stated minimum-degree condition. Prior self-citation to Porte-Sandeep-Santra (CALDAM 2026) is only historical context for the improvement from 4n-3; the new 3n bound and its proof do not reduce to that citation or to any fitted parameter.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard mathematical axioms of combinatorics and the specific problem definitions; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard axioms of graph theory, including that graphs are finite undirected simple graphs without isolated vertices for the stated bound.
    The paper operates within classical graph theory and specifies the no-isolates condition.
  • domain assumption The definition of bicoloration as a map from vertices to {-1,1} and the local inversion operation as described.
    These are the foundational definitions for the color reversal problem.

pith-pipeline@v0.9.1-grok · 5806 in / 1492 out tokens · 40820 ms · 2026-06-27T16:34:48.597843+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 10 canonical work pages

  1. [1]

    Quantum4, 305 (2020).https://doi

    Adcock, J.C., Morley-Short, S., Dahlberg, A., Silverstone, J.W.: Mapping graph state orbits under local complementation. Quantum4, 305 (2020).https://doi. org/10.22331/q-2020-08-07-305

    work page doi:10.22331/q-2020-08-07-305 2020

  2. [2]

    Cabello, A., Parker, M.G., Scarpa, G., Severini, S.: Exclusivity structures and graph representatives of local complementation orbits. J. Math. Phys.54(7), 072202 (2013).https://doi.org/10.1063/1.4813438

    work page doi:10.1063/1.4813438 2013

  3. [3]

    Danielsen, L.E., Parker, M.G.: Edge local complementation and equivalence of binary linear codes. Des. Codes Cryptogr.49(1–3), 161–170 (2008).https://doi. org/10.1007/s10623-008-9190-x

    work page doi:10.1007/s10623-008-9190-x 2008

  4. [4]

    Discrete Math.278(1–3), 45–60 (2004).https://doi

    Ehrenfeucht, A., Harju, T., Rozenberg, G.: Transitivity of local complementation and switching on graphs. Discrete Math.278(1–3), 45–60 (2004).https://doi. org/10.1016/j.disc.2003.04.001

    work page doi:10.1016/j.disc.2003.04.001 2004

  5. [5]

    npj Quantum Inf.5(1), 1–7 (2019).https://doi.org/10.1038/ s41534-019-0191-6

    Hahn, F., Pappa, A., Eisert, J.: Quantum network routing and local comple- mentation. npj Quantum Inf.5(1), 1–7 (2019).https://doi.org/10.1038/ s41534-019-0191-6

    2019

  6. [6]

    In: Graph-Theoretic Concepts in Computer Sci- ence

    Javelle, J., Mhalla, M., Perdrix, S.: On the minimum degree up to local complemen- tation: Bounds and complexity. In: Graph-Theoretic Concepts in Computer Sci- ence. Lecture Notes in Computer Science, vol. 7551, pp. 138–147. Springer (2012). https://doi.org/10.1007/978-3-642-34611-8_16

    work page doi:10.1007/978-3-642-34611-8_16 2012

  7. [7]

    Joo, J., Feder, D.L.: Edge local complementation for logical cluster states. New J. Phys.13(6), 063025 (2011).https://doi.org/10.1088/1367-2630/13/6/063025

    work page doi:10.1088/1367-2630/13/6/063025 2011

  8. [8]

    il Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B95(1), 79–100 (2005).https://doi.org/10.1016/J.JCTB.2005.03.003

    work page doi:10.1016/j.jctb.2005.03.003 2005

  9. [9]

    In: Misra, N., Pandey, A

    Porte, K.S., Sandeep, R.B., Santra, K.: Improved upper bounds on color reversal by local inversions. In: Misra, N., Pandey, A. (eds.) Algorithms and Discrete Applied Mathematics. pp. 428–441. Springer Nature Switzerland, Cham (2026) Tight Upper Bounds on Color Reversal by Local Inversions 13

    2026

  10. [10]

    Discrete Math.64(1), 81– 86 (1987).https://doi.org/10.1016/0012-365X(87)90240-8

    Sabidussi, G.: Color-reversal by local complementation. Discrete Math.64(1), 81– 86 (1987).https://doi.org/10.1016/0012-365X(87)90240-8

    work page doi:10.1016/0012-365x(87)90240-8 1987

  11. [11]

    In: Geometry and Combinatorics: Selected Works of J

    Seidel, J.J.: A survey of two-graphs. In: Geometry and Combinatorics: Selected Works of J. J. Seidel, pp. 146–176. Academic Press (1991).https://doi.org/10. 1016/B978-0-12-189420-7.50018-9

    1991

  12. [12]

    Linear Algebra Appl

    Traldi, L.: On the linear algebra of local complementation. Linear Algebra Appl. 436(5), 1072–1089 (2012).https://doi.org/10.1016/j.laa.2011.06.048

    work page doi:10.1016/j.laa.2011.06.048 2012

  13. [13]

    Traldi, L.: Binary matroids and local complementation. Eur. J. Combin.45, 21–40 (2015).https://doi.org/10.1016/j.ejc.2014.10.001

    work page doi:10.1016/j.ejc.2014.10.001 2015

  14. [14]

    Zhang, J.: Local complementation rule for continuous-variable four-mode un- weighted graph states. Phys. Rev. A78(3), 034301 (2008).https://doi.org/10. 1103/PhysRevA.78.034301

    2008