Representing Graphs via Pattern Avoiding Words

The notion of a word-representable graph has been studied in a series of papers in the literature. A 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. If V =\1, …, n\, this is equivalent to saying that G is word-representable if for all x,y ∈ \1, …, n\, xy ∈ E if and only if the subword w_,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 vertex-labeled 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_,y\ has no consecutive occurrence of the pattern u. Thus, word-representable graphs are just $11$-representable graphs. We show that for any k ≥ 3, every finite graph G is 1ᵏ-representable. This contrasts with the fact that not all graphs are 11-representable graphs.The main focus of the paper is the study of $12$-representable graphs. In particular, we classify the $12$-representable trees. We show that any $12$-representable graph is a comparability graph and the class of $12$-representable graphs include the classes of co-interval graphs and permutation graphs. We also state a number of facts on $12$-representation of induced subgraphs of a grid graph.