Abstract: 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. Agraph G isk-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 Cheonatal. is that 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 111-representation of Chvátal graph, Mycielski graph, split graphs, and graphs whose vertices can be partitioned into a comparability graph and an independent set.

Cite: Kitaev S. , Futorny M. , Pyatkin A.
New Tools to Study 1-11-Representation of Graphs
Graphs and Combinatorics. 2024. V.40. N5. P.1-13. DOI: 10.1007/s00373-024-02825-1 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Mar 24, 2024
Accepted:	Jul 26, 2024
Published print:	Aug 14, 2024
Published online:	Aug 14, 2024

Identifiers:

Web of science:	WOS:001290250900001
Scopus:	2-s2.0-85201262223
Elibrary:	73624013
OpenAlex:	W4401556672

Citing:

DB	Citing
Scopus	1

Altmetrics: