New tools to study 1-11-representation of graphs

Futorny, Mikhail and Kitaev, Sergey and Pyatkin, Artem (2024) New tools to study 1-11-representation of graphs. Graphs and Combinatorics, 40 (5). 97. ISSN 0911-0119 (https://doi.org/10.1007/s00373-024-02825-1)

[thumbnail of Futorny-etal-GC-2024-New-tools-to-study-1-11-representation-of-graphs]
Preview
 Text. Filename: Futorny-etal-GC-2024-New-tools-to-study-1-11-representation-of-graphs.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (376kB)| Preview

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. 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 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.

ORCID iDs

Futorny, Mikhail, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)