Coloring graphs as complete graph invariants
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915338675814400 |
|---|---|
| author | Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. |
| author_facet | Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. |
| contents | We investigate the extent to which the $k$-coloring graph $\mathcal{C}_{k}(G)$ uniquely determines the base graph $G$ and the number of colors $k$. The vertices of $\mathcal{C}_{k}(G)$ are the proper $k$-colorings of $G$, and edges connect colorings that differ on exactly one vertex. There are nonisomorphic graphs $G_1$ and $G_2$ with isomorphic coloring graphs, so $\mathcal{C}_{k}(G)$ is not a complete invariant in general. However, for color palettes with surplus colors (when the number of colors $k$ is greater than the chromatic number), we prove that the coloring graph is a complete invariant. Specifically, provided that $k_1 > χ(G_1)$, we show that $\mathcal{C}_{k_1}(G_1)\cong \mathcal{C}_{k_2}(G_2)$ implies $G_1\cong G_2$ and $k_1=k_2$. Thus, there is a natural bijection between pairs $(G, k)$ with $k > χ(G)$ and their coloring graphs $\mathcal{C}_k(G)$. Furthermore, no coloring graph of the form $\mathcal{C}_{χ(G)}(G)$ is isomorphic to a coloring graph with surplus colors. Our constructive proof provides a method to decide whether a coloring graph is generated with surplus colors, although the resulting algorithms are inefficient. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20978 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coloring graphs as complete graph invariants Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. Combinatorics Primary: 05C15, Secondary: 05C60, 05C85 We investigate the extent to which the $k$-coloring graph $\mathcal{C}_{k}(G)$ uniquely determines the base graph $G$ and the number of colors $k$. The vertices of $\mathcal{C}_{k}(G)$ are the proper $k$-colorings of $G$, and edges connect colorings that differ on exactly one vertex. There are nonisomorphic graphs $G_1$ and $G_2$ with isomorphic coloring graphs, so $\mathcal{C}_{k}(G)$ is not a complete invariant in general. However, for color palettes with surplus colors (when the number of colors $k$ is greater than the chromatic number), we prove that the coloring graph is a complete invariant. Specifically, provided that $k_1 > χ(G_1)$, we show that $\mathcal{C}_{k_1}(G_1)\cong \mathcal{C}_{k_2}(G_2)$ implies $G_1\cong G_2$ and $k_1=k_2$. Thus, there is a natural bijection between pairs $(G, k)$ with $k > χ(G)$ and their coloring graphs $\mathcal{C}_k(G)$. Furthermore, no coloring graph of the form $\mathcal{C}_{χ(G)}(G)$ is isomorphic to a coloring graph with surplus colors. Our constructive proof provides a method to decide whether a coloring graph is generated with surplus colors, although the resulting algorithms are inefficient. |
| title | Coloring graphs as complete graph invariants |
| topic | Combinatorics Primary: 05C15, Secondary: 05C60, 05C85 |
| url | https://arxiv.org/abs/2504.20978 |