Journal of Combinatorics
Volume 12 (2021)
Word-representability of split graphs
Pages: 725 – 746
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 \dotsm$ (of even or odd length) or a word $yxyx \dotsm$ (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 \in 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 wordrepresentable 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.
split graph, word-representation, semi-transitive orientation
2010 Mathematics Subject Classification
Primary 05C62. Secondary 68R15.
Received 15 November 2019
Accepted 15 September 2020
Published 31 January 2022