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)

[thumbnail of Cheon-etal-JC2018-On-k-11-representable-graphs]
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 logoORCID: https://orcid.org/0000-0003-3324-1647 and Pyatkin, Artem;
CORE (COnnecting REpositories)