{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:43:00Z","timestamp":1771026180299,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>The notion of a word-representable graph has been\u00a0studied 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$.\u00a0If $V =\\{1, \\ldots, n\\}$, this is equivalent to saying that\u00a0$G$ is word-representable if for all\u00a0$x,y \\in \\{1, \\ldots, n\\}$, $xy \\in E$ if and only if\u00a0the subword $w_{\\{x,y\\}}$ of $w$ consisting of all occurrences\u00a0of $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\\}^*$. A graph $G$ is $u$-representable if and only if\u00a0there is a vertex-labeled version of $G$, $G=(\\{1, \\ldots, n\\}, E)$,\u00a0and a word $w \\in \\{1, \\ldots, n\\}^*$ such that for\u00a0all $x,y \\in \\{1, \\ldots, n\\}$, $xy \\in E$ if and only if\u00a0$w_{\\{x,y\\}}$ has no consecutive\u00a0occurrence of the pattern $u$. Thus, word-representable\u00a0graphs are just $11$-representable graphs. We show\u00a0that for any $k \\geq 3$, every finite graph $G$ is\u00a0$1^k$-representable. This contrasts with the\u00a0fact that not all graphs are 11-representable graphs.The main focus of the paper is the study of\u00a0$12$-representable graphs.\u00a0In particular, we classify the $12$-representable trees.\u00a0We show that any $12$-representable graph is a\u00a0comparability graph and the class of $12$-representable graphs include the classes of co-interval graphs and permutation graphs.\u00a0We also state a number of facts on $12$-representation of induced subgraphs of a grid graph.<\/jats:p>","DOI":"10.37236\/4946","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T23:41:31Z","timestamp":1578699691000},"source":"Crossref","is-referenced-by-count":6,"title":["Representing Graphs via Pattern Avoiding Words"],"prefix":"10.37236","volume":"22","author":[{"given":"Miles","family":"Jones","sequence":"first","affiliation":[]},{"given":"Sergey","family":"Kitaev","sequence":"additional","affiliation":[]},{"given":"Artem","family":"Pyatkin","sequence":"additional","affiliation":[]},{"given":"Jeffrey","family":"Remmel","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2015,6,15]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i2p53\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i2p53\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T10:15:36Z","timestamp":1579256136000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v22i2p53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,15]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2015,4,14]]}},"URL":"https:\/\/doi.org\/10.37236\/4946","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,15]]},"article-number":"P2.53"}}