2025/02/02 by Dwary, Tithi, Mozhui, Khyodeno, Krishna, K. V.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.00872
A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. The word-representability of split graphs was studied in a series of papers in the literature, and the class of word-representable split graphs was characterized through semi-transitive orientation. Nonetheless, the representation number of this class of graphs is still not known. In general, determining the representation number of a word-representable graph is an NP-complete problem. In this work, through an algorithmic procedure, we show that the representation number of the class of word-representable split graphs is at most three. Further, we characterize the class of word-representable split graphs as well as the class of split comparability graphs which have representation number exactly three.