Existence of u -Representation of Graphs
Sergey Kitaev · Journal of Graph Theory · 2016
Recently, Jones et al. (Electron J Comb 22(2) (2015), #P2.53) introduced the study of u-representable graphs, where u is a word over containing at least one 1. The notion of a u-representable graph is a far-reaching generalization of the notion of a word-representable graph studied in the literature in a series of papers. Jones et al. have shown that any graph is 11⋅⋅⋅1-representable assuming that the number of 1s is at least three, while the class of 12-representable graphs is properly contained in the class of comparability graphs, which, in turn, is properly contained in the class of word-representable graphs corresponding to 11-representable graphs. Further studies in this direction were conducted by Nabawanda (M.Sc. thesis, 2015), who has shown, in particular, that the class of 112-representable graphs is not included in the class of word-representable graphs. Jones et al. raised a question on classification of u-representable graphs at least for small values of u. In this article, we show that if u is of length at least 3 then any graph is u-representable. This rather unexpected result shows that from existence of representation point of view there are only two interesting nonequivalent cases in the theory of u-representable graphs, namely, those of and .