2025/08/21 by Chen, Herman Z. Q., Hameed, Humaira, Kitaev, Sergey · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.15177
Word-representable graphs are a class of graphs that can be represented by words, where edges and non-edges are determined by the alternation of letters in those words. Several papers in the literature have explored the word-representability of split graphs, in which the vertices can be partitioned into a clique and an independent set. In this paper, we initiate the study of the word-representability of graphs in which the vertices can be partitioned into two cliques. We provide a complete characterization of such word-representable graphs in terms of forbidden subgraphs when one of the cliques has a size of at most four. In particular, if one of the cliques is of size four, we prove that there are seven minimal non-word-representable graphs.