Characterization of word-representable split graphs with an independent set of fixed size
Utilitas Mathematica · 22.07.2026 · 128 · 3-31
DOI: 10.61091/um128-01 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 22.07.2026. Verfasst von Suchanda Roy und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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\ldots\) (of even or odd length) or \(yxyx\ldots\) (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 two distinct vertices \(x, y \in V(G)\) are adjacent in \(G\) (i.e., \(xy \in 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 in recent years. Partial progress has been made in characterizing word-representable split graphs through minimal forbidden induced subgraphs, but a complete classification remains open. In this work, we study a specific subclass: split graphs with an independent set of size four, and we provide a minimal forbidden induced subgraph characterization of word-representable graphs in this class as a step towards addressing the broader classification problem. The subclass we study also corresponds to an open problem posed by Kitaev and Pyatkin. In addition, we outline possible approaches and proof strategies that may lead to a complete characterization of word-representable split graphs.
Zitieren
APA
Roy, S., & Hariharasubramanian, R. (2026). Characterization of word-representable split graphs with an independent set of fixed size. Utilitas Mathematica, 128, 3-31. https://doi.org/10.61091/um128-01
Vancouver
Roy S, Hariharasubramanian R. Characterization of word-representable split graphs with an independent set of fixed size. Utilitas Mathematica. 2026;128:3-31. doi:10.61091/um128-01
BibTeX
@article{Roy2026,
author = {Roy, Suchanda and Hariharasubramanian, Ramesh},
title = {Characterization of word-representable split graphs with an independent set of fixed size},
journal = {Utilitas Mathematica},
year = {2026},
volume = {128},
pages = {3--31},
doi = {10.61091/um128-01}
}
EUVIMED