On k11representable graphs
Cheon, GiSang and Kim, Jinha and Kim, Minki and Kitaev, Sergey and Pyatkin, Artem (2019) On k11representable graphs. Journal of Combinatorics, 10 (3). pp. 491513. ISSN 21563527 (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 wordrepresentable 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 k11representable graph for a nonnegative integer k, which generalizes the notion of a wordrepresentable 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, wordrepresentable graphs are precisely 011representable graphs. Our key result in this paper is showing that every graph is 211representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 011representation. Also, we show that the class of wordrepresentable graphs, studied intensively in the literature, is contained strictly in the class of 111representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 111representable 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 011representable graphs that can be represented by uniform words containing two copies of each letter.


Item type: Article ID code: 65577 Dates: DateEvent23 May 2019Published23 September 2018AcceptedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 01 Oct 2018 11:20 Last modified: 21 Feb 2024 15:09 URI: https://strathprints.strath.ac.uk/id/eprint/65577