Representing graphs via pattern avoiding words (Q491554)

Summary: 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,\dots, n\}\), this is equivalent to saying that \(G\) is word-representable if for all \(x,y \in \{1,\dots, n\}\), \(xy \in 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 \in \{1,2\}^\ast\). A graph \(G\) is \(u\)-representable if and only if there is a vertex-labeled version of \(G\), \(G=(\{1,\dots, n\}, E)\), and a word \(w \in \{1,\dots, n\}^\ast\) such that for all \(x,y \in \{1,\dots, n\}\), \(xy \in E\) if and only if \(w_{\{x,y\}}\) has no consecutive occurrence of the pattern \(u\). Thus, word-representable graphs are just \(11\)-representable graphs. We show that for any \(k \geq 3\), every finite graph \(G\) is \(1^k\)-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.