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)
Preview |
Text.
Filename: Futorny-etal-GC-2024-New-tools-to-study-1-11-representation-of-graphs.pdf
Final Published Version License: ![]() 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.
-
-
Item type: Article ID code: 90054 Dates: DateEvent14 August 2024Published26 July 2024AcceptedSubjects: Science > Mathematics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 26 Jul 2024 10:53 Last modified: 28 Aug 2024 06:55 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/90054