Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.27183 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911720788721664 |
|---|---|
| author | Adamson, Duncan Dietz, Amanita Fleischmann, Pamela Huch, Annika Sacher, Silas Cato |
| author_facet | Adamson, Duncan Dietz, Amanita Fleischmann, Pamela Huch, Annika Sacher, Silas Cato |
| contents | This paper investigates the new notion of $2$-word-$π$-repre\-sentable graphs: the nodes of the graph correspond to the letters of the two words and there exists an edge between two nodes if the projections of any two letters of both words are equal. The benefit of not only using one word for a representation as introduced by Kitaev and Pyatkin is that every graph is $2$-word-$π$-representable. We present an algorithm that returns two representing words for any graph. Aside, we show that every permutation graph is representable by two $1$-uniform words and give constructions how graph operations on $2$-word-$π$-representable graphs can be realised on their representing words which give further insights into the representation of cographs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_27183 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $2$-word-$π$-representable Graphs Adamson, Duncan Dietz, Amanita Fleischmann, Pamela Huch, Annika Sacher, Silas Cato Combinatorics Formal Languages and Automata Theory This paper investigates the new notion of $2$-word-$π$-repre\-sentable graphs: the nodes of the graph correspond to the letters of the two words and there exists an edge between two nodes if the projections of any two letters of both words are equal. The benefit of not only using one word for a representation as introduced by Kitaev and Pyatkin is that every graph is $2$-word-$π$-representable. We present an algorithm that returns two representing words for any graph. Aside, we show that every permutation graph is representable by two $1$-uniform words and give constructions how graph operations on $2$-word-$π$-representable graphs can be realised on their representing words which give further insights into the representation of cographs. |
| title | $2$-word-$π$-representable Graphs |
| topic | Combinatorics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2605.27183 |