Abstract: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.
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2605.25733 [math.CO] |
| (or arXiv:2605.25733v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25733 arXiv-issued DOI via DataCite (pending registration) |
From: Ramesh Hariharasubramanian [view email]
[v1]
Mon, 25 May 2026 11:42:35 UTC (14 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。