On the word-representability of Km-Kn graphs

Tools

Chen, Herman Z.Q. and Hameed, Humaira and Kitaev, Sergey (2026) On the word-representability of Km-Kn graphs. Discussiones Mathematicae Graph Theory, 46 (2). pp. 321-339. ISSN 1234-3099 (https://doi.org/10.7151/dmgt.2605)

[thumbnail of Chen-etal-DMGT-2025-On-the-word-representability-of-Km-Kn-graphs]
Preview
 Text. Filename: Chen-etal-DMGT-2025-On-the-word-representability-of-Km-Kn-graphs.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (196kB)| Preview

Abstract

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.

ORCID iDs

Chen, Herman Z.Q., Hameed, Humaira and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)