Characterization of Word-Representable Near-Triangulations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916044761726976 |
|---|---|
| author | Roy, Suchanda Hariharasubramanian, Ramesh |
| author_facet | Roy, Suchanda Hariharasubramanian, Ramesh |
| contents | A graph $G=(V,E)$ is said to be word-representable if there exists a word $w$ over the alphabet $V$ such that two distinct letters $x,y\in V$ alternate in $w$ if and only if $xy \in E$. Word-representable graphs form a well-studied graph class with connections to graph orientations, combinatorics on words, and graph coloring.
A near-triangulation is a planar graph in which every face except the outer face is a triangle. Several subclasses of near-triangulations have previously been investigated in the context of word-representability, including polyomino triangulations, triangulations of rectangular polyominoes with a single domino tile, $K_4$-free near-triangulations, face subdivisions of triangular grid graphs, triangulations of grid-covered cylinder graphs, and chordal near-triangulations.
In this paper, we obtain a complete characterization of word-representable near-triangulations in terms of forbidden induced subgraphs. Our result unifies and extends the previously known characterizations for the above subclasses, while also correcting inaccuracies appearing in earlier works. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25733 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Characterization of Word-Representable Near-Triangulations Roy, Suchanda Hariharasubramanian, Ramesh Combinatorics Discrete Mathematics A graph $G=(V,E)$ is said to be word-representable if there exists a word $w$ over the alphabet $V$ such that two distinct letters $x,y\in V$ alternate in $w$ if and only if $xy \in E$. Word-representable graphs form a well-studied graph class with connections to graph orientations, combinatorics on words, and graph coloring. A near-triangulation is a planar graph in which every face except the outer face is a triangle. Several subclasses of near-triangulations have previously been investigated in the context of word-representability, including polyomino triangulations, triangulations of rectangular polyominoes with a single domino tile, $K_4$-free near-triangulations, face subdivisions of triangular grid graphs, triangulations of grid-covered cylinder graphs, and chordal near-triangulations. In this paper, we obtain a complete characterization of word-representable near-triangulations in terms of forbidden induced subgraphs. Our result unifies and extends the previously known characterizations for the above subclasses, while also correcting inaccuracies appearing in earlier works. |
| title | Characterization of Word-Representable Near-Triangulations |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2605.25733 |