Semi-transitive orientations and word-representable graphs

A graph G=(V,E)G=(V,E) is a word-representable graph   if there exists a word WW over the alphabet VV such that letters xx and yy alternate in WW if and only if (x,y)∈E(x,y)∈E for each x≠yx≠y.In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs.We also explore bounds on the size of the word representing the graph. The representation number of GG is the minimum kk such that GG is a representable by a word, where each letter occurs kk times; such a kk exists for any word-representable graph. We show that the representation number of a word-representable graph on nn vertices is at most 2n2n, while there exist graphs for which it is n/2n/2.