  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
$(x,y)\in E$ for each $x\neq y$. The set of word-representable graphs
generalizes several important and well-studied graph families, such as circle
graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree at
most 3, etc. By answering an open question from [M. Halldorsson, S. Kitaev and
A. Pyatkin, Alternation graphs, Lect. Notes Comput. Sci. 6986 (2011) 191--202.
Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in
Computer Science, WG 2011, Tepla Monastery, Czech Republic, June 21-24, 2011.],
in the present paper we show that not all graphs of vertex degree at most 4 are
word-representable. Combining this result with some previously known facts, we
derive that the number of $n$-vertex word-representable graphs is
$2^{\frac{n^2}{3}+o(n^2)}$.

Combinatorics