# On k-11-representable graphs

Cheon, Gi-Sang and Kim, Jinha and Kim, Minki and Kitaev, Sergey and Pyatkin, Artem (2019) On k-11-representable graphs. Journal of Combinatorics, 10 (3). pp. 491-513. ISSN 2156-3527 (https://doi.org/10.4310/JOC.2019.v10.n3.a3)

 Preview Text. Filename: Cheon_etal_JC2018_On_k_11_representable_graphs.pdf Accepted Author Manuscript Download (317kB)| Preview

## Abstract

Distinct letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word of the form xyxy... (of even or odd length) or a word of the form yxyx... (of even or odd length). A simple graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy. In 2017, Jeff Remmel introduced the notion of a k-11-representable graph for a non-negative integer k, which generalizes the notion of a word-representable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, word-representable graphs are precisely 0-11-representable graphs. Our key result in this paper is showing that every graph is 2-11-representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 0-11-representation. Also, we show that the class of word-representable graphs, studied intensively in the literature, is contained strictly in the class of 1-11-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 1-11-representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 0-11-representable graphs that can be represented by uniform words containing two copies of each letter.

#### ORCID iDs

Cheon, Gi-Sang, Kim, Jinha, Kim, Minki, Kitaev, Sergey ORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
• Item type: Article 65577 DateEvent23 May 2019Published23 September 2018Accepted k-11-representable graph, word-representable graph, Electronic computers. Computer science, Computer Science(all) Science > Mathematics > Electronic computers. Computer science Faculty of Science > Computer and Information Sciences Pure Administrator 01 Oct 2018 11:20 20 Jul 2022 01:15 https://strathprints.strath.ac.uk/id/eprint/65577