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

Sergey Kitaev (Department of Mathematics and Statistics, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Yangjing Long (School of Mathematics and Statistics, Central China Normal University, Hubei, China)

Jun Ma (Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China)

Hehui Wu (Shanghai Center for Mathematical Sciences, Fudan University, Shanghai, China)

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.

Full Text (PDF format)

Received 15 November 2019

Accepted 15 September 2020

Published 31 January 2022