pith. sign in

arxiv: 2604.13005 · v2 · pith:3EQCJ3G2new · submitted 2026-04-14 · 🧮 math.CO

Reconstructing a graph from its Bell colouring graph

Brian Hearn This is my paper

Pith reviewed 2026-05-10 14:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords Bell colouring graphgraph reconstructionindependent set partitionsproper coloringsgraph isomorphismclique partitionschromatic number
0
0 comments X

The pith

Every n-vertex graph with no vertex of degree n-1 is uniquely determined by its Bell colouring graph.

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

The Bell colouring graph B(G) has vertices that are all partitions of V(G) into independent sets, with an edge between two partitions whenever one arises from the other by moving a single vertex to a new part. The paper determines exactly when two finite graphs have isomorphic Bell colouring graphs. In particular, it shows that any finite graph on n vertices without a vertex of degree n-1 is uniquely recoverable from the structure of B(G). The same uniqueness holds for the induced subgraph B_{≥k}(G) of partitions with at least k parts whenever k ≤ n-2. A related result gives uniqueness from the Bell k-colouring graph B_k(G) for graphs whose maximum degree is less than n/9 - 1/3 and k larger than the chromatic number. The statements dualize via complements to partitions into cliques.

Core claim

The Bell colouring graph B(G) is the graph whose vertices are the partitions of V(G) into independent sets, with two partitions adjacent precisely when one is obtained from the other by changing the part of a single vertex. The paper determines precisely when two finite graphs have isomorphic Bell colouring graphs. In particular, every n-vertex graph G with no vertices of degree n-1 is uniquely determined by B(G), and by its upper-Bell colouring graph B_{≥k}(G) if k ≤ n-2. Every n-vertex graph with maximum degree Δ(G) < n/9 - 1/3 is uniquely determined by B_k(G) whenever k > χ(G). By taking complements, the results restate in terms of partitions into cliques.

What carries the argument

The Bell colouring graph B(G), whose vertices are partitions of V(G) into independent sets and whose edges record single-vertex part changes, serving as a complete invariant under the stated degree conditions.

If this is right

  • Any n-vertex graph without a universal vertex can be reconstructed exactly from the full Bell colouring graph B(G).
  • Reconstruction remains possible from the upper-Bell subgraph B_{≥k}(G) alone when k ≤ n-2.
  • Graphs whose maximum degree is less than n/9 - 1/3 are determined by their restricted Bell k-colouring graph B_k(G) for any k larger than the chromatic number.
  • All of the above statements have equivalent forms for partitions into cliques obtained by taking complements.

Where Pith is reading between the lines

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

  • The result implies that the connectivity structure of the space of all proper colorings can serve as a complete invariant for the large class of graphs without universal vertices.
  • For graphs that do contain universal vertices, the Bell colouring graph loses distinguishing power and may need to be supplemented with additional data to recover uniqueness.
  • Similar reconstruction questions could be asked for other natural subgraphs or quotients of the Bell colouring graph, such as those restricted to exactly k parts.

Load-bearing premise

The graphs are finite and have no vertex of degree n-1, because the presence of such a universal vertex allows non-unique reconstructions from the Bell colouring graph.

What would settle it

Two non-isomorphic n-vertex graphs, both free of degree-(n-1) vertices, whose Bell colouring graphs are isomorphic would falsify the uniqueness claim.

Figures

Figures reproduced from arXiv: 2604.13005 by Brian Hearn.

Figure 1
Figure 1. Figure 1: The situation in the proof of Lemma 2.5. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The situation in the proof of Lemma 2.8 if [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The situation in the proof of Lemma 2.8 if [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The five types of neighbours Q of a P ∗ -candidate P. For each type, the dashed line represents the non-edge ψP (Q) ∈ E(G). Lemma 2.13. Let P ∈ Ω3. Then ψP is well-defined and injective. Moreover, ψP∗ is bijective. Proof. By Lemma 2.9, every non-edge uv ∈ E(G) either lies within a part of P of size 3 or 2, or between a part of P of size 2 and a part of P of size 1, or between two parts of P of size 1. If P… view at source ↗
Figure 5
Figure 5. Figure 5: A situation in the proof of Lemma 3.4. An edge [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗
read the original abstract

The Bell colouring graph $\mathcal{B}(G)$ of a graph $G$ is the graph whose vertices are the partitions of the vertex set of $G$ into independent sets, with an edge between two partitions if and only if one can be obtained from the other by changing the part of a single vertex of $G$. Given a natural number $k$, the Bell $k$-colouring graph $\mathcal{B}_k(G)$ and the upper-Bell $k$-colouring graph $\mathcal{B}_{\geq k}(G)$ are the induced subgraphs of $\mathcal{B}(G)$ consisting of all partitions with at most $k$ parts and at least $k$ parts, respectively. We determine precisely when two finite graphs have isomorphic Bell colouring graphs. In particular, we show that every $n$-vertex graph $G$ with no vertices of degree $n-1$ is uniquely determined by its Bell colouring graph $\mathcal{B}(G)$, and by its upper-Bell colouring graph $\mathcal{B}_{\geq k}(G)$ if $k\leq n-2$. We also show that every $n$-vertex graph with maximum degree $\Delta(G)< \frac{1}{9}n-\frac{1}{3}$ is uniquely determined by its Bell $k$-colouring graph $\mathcal{B}_k(G)$ if $k>\chi(G)$. By taking graph complements, each of these results can be restated in terms of partitions into cliques.

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 / 3 minor

Summary. The paper defines the Bell colouring graph B(G) of a graph G as the graph whose vertices are the partitions of V(G) into independent sets, with an edge between two partitions if one is obtained from the other by moving a single vertex to a different part. It determines precisely when two finite graphs have isomorphic Bell colouring graphs. In particular, every n-vertex graph G with no vertex of degree n-1 is uniquely determined by B(G) and by the upper-Bell colouring graph B_{≥k}(G) whenever k ≤ n-2. It further shows that every n-vertex graph with Δ(G) < (1/9)n - 1/3 is uniquely determined by its Bell k-colouring graph B_k(G) for k > χ(G). The results extend to clique partitions by taking complements.

Significance. If the stated uniqueness theorems hold, the work supplies a clean reconstruction result that identifies exactly when the reconfiguration graph of independent-set partitions determines the original edge set. The no-degree-(n-1) condition is a natural and explicit hypothesis that prevents universal vertices from collapsing distinctions among partitions; the extension to upper-Bell subgraphs for k ≤ n-2 and to bounded-degree graphs via B_k(G) broadens the result without introducing free parameters or post-hoc adjustments. The complement formulation for clique partitions is a straightforward but useful duality. These features make the contribution a precise addition to the literature on graph invariants and reconfiguration.

minor comments (3)
  1. The abstract asserts that the authors 'determine precisely when two finite graphs have isomorphic Bell colouring graphs,' yet the displayed theorems cover only the no-degree-(n-1) case and the bounded-degree case; a concise statement of the complete characterization (or an explicit note that the listed results are the main cases) would improve clarity.
  2. Notation for the three families (B(G), B_k(G), B_{≥k}(G)) is introduced in the abstract but would benefit from a single consolidated definition paragraph early in the introduction, including the precise meaning of 'changing the part of a single vertex' and the induced-subgraph relation.
  3. The final sentence on complements is stated without indicating whether the proofs are verbatim duals or require separate verification; a short remark on this point would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision for our manuscript on reconstructing graphs from their Bell colouring graphs. We are pleased that the uniqueness theorems, the no-degree-(n-1) condition, the extensions to upper-Bell and bounded-degree cases, and the complement formulation for clique partitions were viewed favorably. Since the report lists no explicit major comments, the point-by-point section below is empty. We will address any minor issues in the revised version.

Circularity Check

0 steps flagged

No significant circularity in the uniqueness theorems

full rationale

The manuscript establishes uniqueness of finite graphs G (under the explicit no-degree-(n-1) condition) from the isomorphism type of B(G) by directly exhibiting how the edge relation in B(G) encodes allowable single-vertex transfers between independent-set partitions, thereby recovering the edge set of G. This is a self-contained combinatorial argument with no fitted parameters, no self-citations invoked as load-bearing premises, and no redefinition of the target object in terms of the claimed reconstruction. The same direct encoding extends to the upper-Bell and bounded-degree variants. The derivation therefore contains no reduction of any prediction or uniqueness statement to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard definitions of graphs, independent sets, partitions, and the induced subgraphs B_k(G) and B_{≥k}(G); no free parameters or new entities are introduced.

axioms (1)
  • standard math Finite graphs and the standard definitions of independent sets, proper partitions, and the adjacency rule in the Bell colouring graph.
    These are the background notions used to define B(G) and the uniqueness statements.

pith-pipeline@v0.9.0 · 5555 in / 1143 out tokens · 49158 ms · 2026-05-10T14:45:16.129235+00:00 · methodology

discussion (0)

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