Existence of u ‐Representation of Graphs

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 { 1 , 2 } 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 u = 11 and u = 12 .