Representing split graphs by words

Herman Z.Q. Chen, Sergey Kitaev, Akira Saito

Research output: Contribution to journalArticle

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.
Original languageEnglish
JournalDiscussiones Mathematicae Graph Theory
Publication statusAccepted/In press - 17 Jun 2020

Keywords

  • split graphs
  • word-representability
  • semi-transitive orientation

Fingerprint Dive into the research topics of 'Representing split graphs by words'. Together they form a unique fingerprint.

  • Cite this

    Chen, H. Z. Q., Kitaev, S., & Saito, A. (Accepted/In press). Representing split graphs by words. Discussiones Mathematicae Graph Theory.