2025/07/11 by Roy, Suchanda, Hariharasubramanian, Ramesh · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.08483
A pair of letters x and y are said to alternate in a word w if, after removing all letters except for the copies of x and y from w, the resulting word is of the form xyxy… (of even or odd length) or yxyx… (of even or odd length). A graph G = (V (G), E(G)) is word-representable if there exists a word w over the alphabet V(G), such that any two distinct vertices x, y ∈ V (G) are adjacent in G (i.e., xy ∈ E(G)) if and only if the letters x and y alternate in w. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Word-representability of split graphs has been studied in a series of papers [2, 5, 7, 9] in the literature. In this work, we give a minimal forbidden induced subgraph characterization of word-representable split graphs with an independent set of size 4, which is an open problem posed by Kitaev and Pyatkin in [9]