New results on word-representable graphs

DOI10.1016/J.DAM.2014.10.024MaRDI QIDQ344843zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Vadim Lozin, Andrew Collins

Publication date 24 November 2016

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

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

zbMATH Keywords

semi-transitive orientationhereditary property of graphsspeed of hereditary properties

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

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)}$.

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

Cites work

• scientific article; zbMATH DE number 3825706 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• Alternation graphs
• Graph Classes: A Survey
• Graphs Capturing Alternations in Words
• Monoids with sub-log-exponential free spectra.
• On representable graphs
• On the Representability of Line Graphs
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Range of values of the entropy of hereditary classes of graphs
• The speed of hereditary properties of graphs
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Word-representability of line graphs

Cited in

(20)

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

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)