Reconstructing a graph from its Bell colouring graph
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915937213480960 |
|---|---|
| author | Hearn, Brian |
| author_facet | Hearn, Brian |
| contents | 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 $Δ(G)< \frac{1}{9}n-\frac{1}{3}$ is uniquely determined by its Bell $k$-colouring graph $\mathcal{B}_k(G)$ if $k>χ(G)$. By taking graph complements, each of these results can be restated in terms of partitions into cliques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13005 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reconstructing a graph from its Bell colouring graph Hearn, Brian Combinatorics 05C60 (Primary) 05C15, 05C69 (Secondary) 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 $Δ(G)< \frac{1}{9}n-\frac{1}{3}$ is uniquely determined by its Bell $k$-colouring graph $\mathcal{B}_k(G)$ if $k>χ(G)$. By taking graph complements, each of these results can be restated in terms of partitions into cliques. |
| title | Reconstructing a graph from its Bell colouring graph |
| topic | Combinatorics 05C60 (Primary) 05C15, 05C69 (Secondary) |
| url | https://arxiv.org/abs/2604.13005 |