Word-representability of split graphs

Sergey Kitaev, Yangjing Long, Jun Ma, Hehui Wu

Research output: Contribution to journalArticlepeer-review

15 Downloads (Pure)

Abstract

Two letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word xyxy⋯ (of even or odd length) or a word yxyx⋯ (of even or odd length). 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 xy∈E. It is known that a graph is word-representable if and only if it admits a certain orientation called semi-transitive orientation.

Word-representable graphs generalize several important classes of graphs such as 3
-colorable graphs, circle graphs, and comparability graphs. There is a long line of research in the literature dedicated to word-representable graphs. However, almost nothing is known on word-representability of split graphs, that is, graphs in which the vertices can be partitioned into a clique and an independent set. In this paper, we shed a light to this direction. In particular, we characterize in terms of forbidden subgraphs word-representable split graphs in which vertices in the independent set are of degree at most 2, or the size of the clique is 4. Moreover, we give necessary and sufficient conditions for an orientation of a split graph to be semi-transitive.
Original languageEnglish
Pages (from-to)725–746
Number of pages22
JournalJournal of Combinatorics
Volume12
Issue number4
DOIs
Publication statusPublished - 31 Jan 2022

Keywords

  • split graph
  • word-representability
  • semi-transitive orientation
  • combinatorics

Fingerprint

Dive into the research topics of 'Word-representability of split graphs'. Together they form a unique fingerprint.

Cite this