2024/07/25 by Mikhail Futorny, Futorny, Mikhail, Sergey Kitaev +3 · 1 citation
Computer Science · #Computer science #Constraint Satisfaction and Optimization #Digital Image Processing Techniques #Graph Theory and Algorithms #Political science #Representation (politics)
paper · pdf · doi:10.48550/arxiv.2407.17784
openalex publication_date 2024/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The notion of a k-11-representable graph was introduced by Jeff Remmel in 2017 and studied by Cheon et al. in 2019 as a natural extension of the extensively studied notion of word-representable graphs, which are precisely 0-11-representable graphs. A graph G is k-11-representable if it can be represented by a word w such that for any edge (resp., non-edge) xy in G the subsequence of w formed by x and y contains at most k (resp., at least k+1) pairs of consecutive equal letters. A remarkable result of Cheon at al. is that \em any graph is 2-11-representable, while it is unknown whether every graph is 1-11-representable. Cheon et al. showed that the class of 1-11-representable graphs is strictly larger than that of word-representable graphs, and they introduced a useful toolbox to study 1-11-representable graphs. In this paper, we introduce new tools for studying 1-11-representation of graphs. We apply them for establishing 1-11-representation of Chvátal graph, Mycielski graph, split graphs, and graphs whose vertices can be partitioned into a comparability graph and an independent set.