Abstract: There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of 9 forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.
Recommendations
- Word-representability of split graphs
- Word-representability of split graphs generated by morphisms
- Word-Representable Graphs: a Survey
- Structural properties of word representable graphs
- Representing graphs via pattern avoiding words
- On word-representable and multi-word-representable graphs
- Word-representability of line graphs
- Splitting digraphs
- New results on word-representable graphs
- Split graphs
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- A comprehensive introduction to the theory of word-representable graphs
- Semi-transitive orientations and word-representable graphs
- Threshold graphs and related topics
- Word-representability of split graphs
- Words and graphs
Cited in
(6)
This page was built for publication: Representing split graphs by words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158202)
