2015/07/12 by Sergey Kitaev, Kitaev, Sergey · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #Generalization #Graph #Graph Labeling and Dimension Problems #Graph product #Graph theory and applications #Indifference graph #Line graph #Mathematics #Pathwidth #math.CO
paper · pdf · doi:10.48550/arxiv.1507.03177
published in arXiv (Cornell University) (Cornell University) · arXiv admin note: text overlap with arXiv:1412.4994
arxiv created 2015/07/12 · openalex publication_date 2015/07/12 · arxiv updated 2015/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Jones et al. 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-rerpesentable 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, 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 paper 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 non-equivalent cases in the theory of u-representable graphs, namely, those of u=11 and u=12.