Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908744852439040 |
|---|---|
| author | Cheng, Christine T. Lambert, Chelsea Ann |
| author_facet | Cheng, Christine T. Lambert, Chelsea Ann |
| contents | A graph that is completely determined by its degree sequence is called a unigraph. In 2000, Regina Tyshkevich published one of the most important papers on unigraphs. There are two parts to the paper: a decomposition theorem that describes how every graph can be broken into a sequence of basic graphs and a complete classification of all basic unigraphs. Together, they reveal how every unigraph is constructed. We provide an informal overview of Tyshkevich's results and show how they enable the computation of various graph parameters of unigraphs in linear time. We also created a toolkit (https://chelseal11.github.io/tyshkevich_decomposition_toolkit/) that implements the algorithms described in this write-up. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00957 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit Cheng, Christine T. Lambert, Chelsea Ann Combinatorics Discrete Mathematics 05C85 F.2.2 A graph that is completely determined by its degree sequence is called a unigraph. In 2000, Regina Tyshkevich published one of the most important papers on unigraphs. There are two parts to the paper: a decomposition theorem that describes how every graph can be broken into a sequence of basic graphs and a complete classification of all basic unigraphs. Together, they reveal how every unigraph is constructed. We provide an informal overview of Tyshkevich's results and show how they enable the computation of various graph parameters of unigraphs in linear time. We also created a toolkit (https://chelseal11.github.io/tyshkevich_decomposition_toolkit/) that implements the algorithms described in this write-up. |
| title | Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit |
| topic | Combinatorics Discrete Mathematics 05C85 F.2.2 |
| url | https://arxiv.org/abs/2601.00957 |