Contents Online

# Journal of Combinatorics

## Volume 12 (2021)

### Number 4

### Word-representability of split graphs

Pages: 725 – 746

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n4.a6

#### Authors

#### 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 \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.

#### Keywords

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