Graphs Identifiable by Degree Sequence and Chromatic Number
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909218196422656 |
|---|---|
| author | Whitman, R. |
| author_facet | Whitman, R. |
| contents | Unigraphs are graphs identifiable up to isomorphism from their degree sequences. Given a class $\mathcal{A}$ of graphs, we define the class of $\mathcal{A}$-unigraphs to be graphs identifiable from degree sequence and membership in $\mathcal{A}$. While these classes are often not hereditary, we provide characterizations of the largest hereditary subclass contained in the bipartite-unigraphs, the $k$-partite unigraphs, the perfect-unigraphs, and the chordal-unigraphs. We also characterize the largest hereditary subclass contained in the bipartite-unigraphs in terms of structure, degree sequence, and a partial order on degree sequences due to Rao. Lastly, we show that all unigraphs $G$ satisfy the bound $χ(G) \le ω(G) + 1$ and are hence apex-perfect graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03667 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graphs Identifiable by Degree Sequence and Chromatic Number Whitman, R. Combinatorics 05C75 (05C07, 05C15, 05C17) Unigraphs are graphs identifiable up to isomorphism from their degree sequences. Given a class $\mathcal{A}$ of graphs, we define the class of $\mathcal{A}$-unigraphs to be graphs identifiable from degree sequence and membership in $\mathcal{A}$. While these classes are often not hereditary, we provide characterizations of the largest hereditary subclass contained in the bipartite-unigraphs, the $k$-partite unigraphs, the perfect-unigraphs, and the chordal-unigraphs. We also characterize the largest hereditary subclass contained in the bipartite-unigraphs in terms of structure, degree sequence, and a partial order on degree sequences due to Rao. Lastly, we show that all unigraphs $G$ satisfy the bound $χ(G) \le ω(G) + 1$ and are hence apex-perfect graphs. |
| title | Graphs Identifiable by Degree Sequence and Chromatic Number |
| topic | Combinatorics 05C75 (05C07, 05C15, 05C17) |
| url | https://arxiv.org/abs/2406.03667 |