2013/07/06 by Andrew Collins, Collins, Andrew, Sergey Kitaev +3 · 3 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #semigroups and automata theory
paper · doi:10.48550/arxiv.1307.1810
openalex publication_date 2013/07/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)∈ E for each x≠ 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(n2)/(3)+o(n2).