New results on word-representable graphs

DOI10.1016/J.DAM.2014.10.024zbMATH Open1350.05143arXiv1307.1810OpenAlexW2086223441MaRDI QIDQ344843FDOQ344843

Andrew Collins, Vadim Lozin, Sergey Kitaev

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: 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)inE$ for each $xeqy$. 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)}$.

Full work available at URL: https://arxiv.org/abs/1307.1810

Recommendations

• Word-Representable Graphs: a Survey
• On representable graphs
• A comprehensive introduction to the theory of word-representable graphs
• Semi-transitive orientations and word-representable graphs
• Solving computational problems in the theory of word-representable graphs

zbMATH Keywords

semi-transitive orientationhereditary property of graphsspeed of hereditary properties

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Cites Work

• Graph Classes: A Survey
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Alternation Graphs
• Graphs Capturing Alternations in Words
• On the Representability of Line Graphs
• Word-Representability of Line Graphs
• On representable graphs
• Word problem of the Perkins semigroup via directed acyclic graphs.
• The speed of hereditary properties of graphs
• Monoids with sub-log-exponential free spectra.
• Range of values of the entropy of hereditary classes of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (15)

• Word-representability of Toeplitz graphs
• A comprehensive introduction to the theory of word-representable graphs
• The connective eccentricity index and modified second Zagreb index of Parikh word representable graphs
• Representing split graphs by words
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• Certain distance-based topological indices of Parikh word representable graphs
• Word-Representable Graphs: a Survey
• Word-representable graphs from a word's perspective
• On word-representability of polyomino triangulations
• Representing graphs via pattern avoiding words
• Wiener-type indices of Parikh word representable graphs
• On semi-transitive orientability of Kneser graphs and their complements
• Solving computational problems in the theory of word-representable graphs
• On graphs representable by pattern-avoiding words

This page was built for publication: New results on word-representable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344843)