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). ISSN 10778926

Text (JonesetalEJOC2015Representinggraphsviapatternavoidingwords)
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.
Item type:  Article 

ID code:  53422 
Keywords:  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 > Mathematics 
Department:  Faculty of Science > Computer and Information Sciences 
Depositing user:  Pure Administrator 
Date deposited:  18 Jun 2015 13:54 
Last modified:  06 Mar 2018 07:46 
Related URLs:  
URI:  https://strathprints.strath.ac.uk/id/eprint/53422 
Export data: 