$2$-word-$π$-representable Graphs
This work extends the concept of word-representable graphs to a new representation that covers all graphs, offering a universal representation scheme.
The paper introduces 2-word-π-representable graphs, proving that every graph is representable by two words, and provides an algorithm to construct such words for any graph.
This paper investigates the new notion of $2$-word-$π$-repre\-sentable graphs: the nodes of the graph correspond to the letters of the two words and there exists an edge between two nodes if the projections of any two letters of both words are equal. The benefit of not only using one word for a representation as introduced by Kitaev and Pyatkin is that every graph is $2$-word-$π$-representable. We present an algorithm that returns two representing words for any graph. Aside, we show that every permutation graph is representable by two $1$-uniform words and give constructions how graph operations on $2$-word-$π$-representable graphs can be realised on their representing words which give further insights into the representation of cographs.