Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.19493 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916809562652672 |
|---|---|
| author | Böll, Philipp Fleischmann, Pamela Huch, Annika Kreiß, Jana Löck, Tim Park, Kajus Wiedenhöft, Max |
| author_facet | Böll, Philipp Fleischmann, Pamela Huch, Annika Kreiß, Jana Löck, Tim Park, Kajus Wiedenhöft, Max |
| contents | In this work, we investigate the relationship between $k$-repre\-sentable graphs and graphs representable by $k$-local words. In particular, we show that every graph representable by a $k$-local word is $(k+1)$-representable. A previous result about graphs represented by $1$-local words is revisited with new insights. Moreover, we investigate both classes of graphs w.r.t. hereditary and in particular the speed as a measure. We prove that the latter ones belong to the factorial layer and that the graphs in this classes have bounded clique-width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19493 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Word-Representable Graphs and Locality of Words Böll, Philipp Fleischmann, Pamela Huch, Annika Kreiß, Jana Löck, Tim Park, Kajus Wiedenhöft, Max Combinatorics Formal Languages and Automata Theory In this work, we investigate the relationship between $k$-repre\-sentable graphs and graphs representable by $k$-local words. In particular, we show that every graph representable by a $k$-local word is $(k+1)$-representable. A previous result about graphs represented by $1$-local words is revisited with new insights. Moreover, we investigate both classes of graphs w.r.t. hereditary and in particular the speed as a measure. We prove that the latter ones belong to the factorial layer and that the graphs in this classes have bounded clique-width. |
| title | Word-Representable Graphs and Locality of Words |
| topic | Combinatorics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2506.19493 |