pith. sign in

arxiv: 2604.13005 · v1 · 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.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Coloring graphs as com- plete graph invariants

    Shamil Asgarli, Sara Krehbiel, and Howard W Levinson. “Coloring graphs as com- plete graph invariants”.arXiv preprint arXiv:2504.20978(2025). 27

    work page arXiv 2025

  2. [2]

    Counting subgraphs of coloring graphs

    Shamil Asgarli, Sara Krehbiel, Howard W. Levinson, and Heather M. Russell. “Counting subgraphs of coloring graphs”.Graphs and Combinatorics41.4 (2025), Paper No. 82, 38

    work page 2025

  3. [3]

    Bell coloring graphs: realiz- ability and reconstruction

    Shamil Asgarli, Sara Krehbiel, and Simon MacLean. “Bell coloring graphs: realiz- ability and reconstruction”.arXiv preprint arXiv:2512.10177(2025)

    work page arXiv 2025

  4. [4]

    Determining a graph from its reconfiguration graph

    Gaétan Berthe, Caroline Brosse, Brian Hearn, Jan van den Heuvel, Pierre Hop- penot, and Théo Pierron. “Determining a graph from its reconfiguration graph”. arXiv preprint arXiv:2504.19783(2025)

    work page arXiv 2025

  5. [5]

    Connectedness of the graph of vertex-colourings

    Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. “Connectedness of the graph of vertex-colourings”.Discrete Mathematics308.5-6 (2008), 913–919

    work page 2008

  6. [6]

    Gray code numbers for graphs

    Kelly Choo and Gary MacGillivray. “Gray code numbers for graphs”.Ars Mathe- matica Contemporanea4.1 (2011), 125–139

    work page 2011

  7. [7]

    Randomly coloring sparse random graphs with fewer colors than the maximum degree

    Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda. “Randomly coloring sparse random graphs with fewer colors than the maximum degree”.Ran- dom Structures & Algorithms29.4 (2006), 450–465

    work page 2006

  8. [8]

    Hamiltonicity of Bell and Stirling colour graphs

    Stephen Finbow and Gary MacGillivray. “Hamiltonicity of Bell and Stirling colour graphs”.arXiv preprint arXiv:2512.13864(2025)

    work page arXiv 2025

  9. [9]

    The canonical coloring graph of trees and cycles

    Ruth Haas. “The canonical coloring graph of trees and cycles”.Ars Mathematica Contemporanea5.1 (2012), 149–157

    work page 2012

  10. [10]

    Proof of a conjecture of P. Erdős

    András Hajnal and Endre Szemerédi. “Proof of a conjecture of P. Erdős”. In:Com- binatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969). Vol. 4. Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam-London, 1970, pp. 601–623

    work page 1969

  11. [11]

    The complexity of change

    Jan van den Heuvel. “The complexity of change”. In:Surveys in Combinatorics

    work page

  12. [12]

    Press, Cambridge, 2013, pp

    Cambridge Univ. Press, Cambridge, 2013, pp. 127–160

    work page 2013

  13. [13]

    A note on graphs of k-colourings

    Emma Hogan, Alex Scott, Youri Tamitegama, and Jane Tan. “A note on graphs of k-colourings”.Electronic Journal of Combinatorics31.4 (2024), Paper No. 4.48, 9

    work page 2024

  14. [14]

    Introductiontoreconfiguration

    NaomiNishimura.“Introductiontoreconfiguration”.Algorithms (Basel)11.4(2018), Paper No. 52, 25

    work page 2018

  15. [15]

    Congruent graphs and the connectivity of graphs

    Hassler Whitney. “Congruent graphs and the connectivity of graphs”.American Journal of Mathematics54.1 (1932), 150–168. 28 A Strengthening Theorem 1.5 In this appendix, we will strengthen Theorem 1.5 by giving a complete classification of the pairs of tuples(G1, k1)and(G 2, k2)such that the upper-Bellk 1-colouring graph ofG 1 is isomorphic to the upper-Be...

    work page 1932

  16. [16]

    The result follows by Observation 2.22

    ∼= B≥n′ 2−1(G′ 2). The result follows by Observation 2.22. We now prove one direction of Theorem A.1. Proof of Theorem A.1, ‘if’ direction.We show thatB≥k1(G1) ∼= B≥k2(G2)in each of the eight cases. Leti∈ {1,2}be fixed

    work page

  17. [17]

    ThenB ≥ki(G)is the empty graph with no vertices

    Suppose thatk i > n i. ThenB ≥ki(G)is the empty graph with no vertices

    work page

  18. [18]

    ThenB ≥ki(G)is a graph on a single vertex

    Suppose that eitherki =n i, orG i is a clique andki ≤n i. ThenB ≥ki(G)is a graph on a single vertex

    work page

  19. [19]

    Then the claim follows by Lemma A.2

    Suppose thatG 1 ∼= G2 andk i =n i −1. Then the claim follows by Lemma A.2

    work page

  20. [20]

    Then the claim follows by Lemma 2.24

    Suppose thatG ′ 1 ∼= G′ 2, and thatχ(Gi) + 1≤k i ≤n i −2, andn 1 −k 1 =n 2 −k 2. Then the claim follows by Lemma 2.24

    work page

  21. [21]

    Then for eachi∈ {1,2}we haveB ≥ki(Gi) ∼= B(Gi), and so the claim follows by Theorem 1.4

    Suppose thatG ′ 1 ∼= G′ 2, and thatk i ≤χ(G i). Then for eachi∈ {1,2}we haveB ≥ki(Gi) ∼= B(Gi), and so the claim follows by Theorem 1.4

    work page

  22. [22]

    Letvbe the unique vertex in theK 1 component ofG ′ i

    Suppose thatk i ≤n i −1, and thatG ′ i ∼= KN +K 1 for someN≥1. Letvbe the unique vertex in theK 1 component ofG ′ i. Then there are exactlyNpartitions P∈V(B), namely the partitionP ∗ intoN+ 1parts of size1, and theNpartitions where|P(v)|= 2and every other part has size1. Moreover, each of these partitions are adjacent to each other. HenceB≥k1(Gi)is a cliq...

    work page

  23. [23]

    Then in both cases, there are exactly four partitions ofG′ i into at leastk i parts, and these partitions are all adjacent to each other inB≥k1(Gi)

    Suppose that eitherk i ≤n i −1andG ′ i ∼= K3 +K 1, ork i =n i −1andG ′ i ∼= K3. Then in both cases, there are exactly four partitions ofG′ i into at leastk i parts, and these partitions are all adjacent to each other inB≥k1(Gi). HenceB ≥k1(Gi)is isomorphic to the cliqueK4

    work page

  24. [24]

    Then in both cases, there are exactly five partitions ofG′ i into at leastk i parts, and with one exception these partitions are all adjacent to each other inB≥k1(Gi)

    Suppose eitherk i ≤n i −2andG ′ i ∼= K3, ork i =n i −1andG ′ i ∼= P3 +K 1. Then in both cases, there are exactly five partitions ofG′ i into at leastk i parts, and with one exception these partitions are all adjacent to each other inB≥k1(Gi). HenceB ≥k1(Gi)is isomorphic toK − 5 , defined as the graph formed by removing any edge from the cliqueK5. It remai...

    work page