EUVIMEDEUVIMED entdecken
Crossref

Characterization of word-representable split graphs with an independent set of fixed size

Suchanda Roy, Ramesh Hariharasubramanian

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →