Word-representability of split graphs

Sergey Kitaev, Yangjing Long, Jun Ma, Hehui Wu

Research output: Contribution to journalArticle

2 Downloads (Pure)

Abstract

Two letters x and y alternate in a word w if after deleting in wall 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). Agraph G = (V;E) is word-representable if there exists a word w overthe alphabet V such that letters x and y alternate in w if and only ifxy 2 E. It is known that a graph is word-representable if and only ifit admits a certain orientation called semi-transitive orientation.Word-representable graphs generalize several important classes ofgraphs such as 3-colorable graphs, circle graphs, and comparabilitygraphs. There is a long line of research in the literature dedicatedto word-representable graphs. However, almost nothing is known onword-representability of split graphs, that is, graphs in which the ver-tices can be partitioned into a clique and an independent set. In thispaper, we shed a light to this direction. In particular, we character-ize in terms of forbidden subgraphs word-representable split graphsin which vertices in the independent set are of degree at most 2, orthe size of the clique is 4. Moreover, we give necessary and sucientconditions for an orientation of a split graph to be semi-transitive.
Original languageEnglish
Number of pages21
JournalJournal of Combinatorics
Publication statusAccepted/In press - 14 Sep 2020

Keywords

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

Cite this