Representing graphs via pattern avoiding words
Jones, Miles and Kitaev, Sergey and Pyatkin, Artem and Remmel, Jeffrey (2015) Representing graphs via pattern avoiding words. The Electronic Journal of Combinatorics, 22 (2). P2.53. ISSN 10778926
Preview 
Text.
Filename: Jones_etal_EJOC_2015_Representing_graphs_via_pattern_avoiding_words.pdf
Accepted Author Manuscript Download (273kB) Preview 
Abstract
The notion of a wordrepresentable graph has been studied in a series of papers in the literature. A 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 . If V = {1,...,n}, this is equivalent to saying that G is wordrepresentable if for all x,y ϵ {1,…,n}, xy ϵ E if and only if the subword w {x,y} of w consisting of all occurrences of x or y in w has no consecutive occurrence of the pattern 11. In this paper, we introduce the study of u representable graphs for any word u ϵ {1, 2}*. A graph G is u representable if and only if there is a vertexlabeled version of G, G = ( {1,…,n},E ), and a word w ϵ {1,…,n}* such that for all x,y ϵ {1,…,n}, xy ϵ E if and only if w {x,y} has no consecutive occurrence of the pattern u . Thus, wordrepresentable graphs are just 11representable graphs. We show that for any k > 3, every finite graph G is 1 k  representable. This contrasts with the fact that not all graphs are 11representable graphs. The main focus of the paper is the study of 12representable graphs. In particular, we classify the 12representable trees. We show that any 12representable graph is a comparability graph and the class of 12representable graphs include the classes of cointerval graphs and permutation graphs. We also state a number of facts on 12representation of induced subgraphs of a grid graph.
ORCID iDs
Jones, Miles, Kitaev, Sergey ORCID: https://orcid.org/0000000333241647, Pyatkin, Artem and Remmel, Jeffrey;

Item type: Article ID code: 53422 Dates: DateEvent2015Published15 June 2015Published Online25 May 2015AcceptedKeywords: wordrepresentable graphs, ladder graphs, grid graphs, permutation graphs, cointerval graphs, comparability graphs, pattern avoidance, Electronic computers. Computer science, Mathematics, Computational Theory and Mathematics Subjects: Science > Mathematics > Electronic computers. Computer science
Science > MathematicsDepartment: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 18 Jun 2015 13:54 Last modified: 27 Jan 2022 01:39 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/53422