RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2007 Volume 15, Number 1, Pages 91–97 (Mi timb87)

This article is cited in 1 paper

Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs

T. V. Lubashevaa, Yu. M. Metelskyb

a Belarusian State Economic University
b Belarusian State University

Abstract: It is proved that, for an arbitrary fixed $k\ge3$, the class $L^l(k)$ of graphs with equivalence partition number at most $k$ can be characterized by means of a finite list of forbidden induced subgraphs in an extension of the class of split graphs — the class of $\mathcal{U}$-split graphs. In the case $k=3$ the corresponding list as well as a description of the graphs in $L^l(3)$ in the class of $\mathcal{U}$-split graphs not being split are obtained.

UDC: 519.1

Received: 23.11.2006



© Steklov Math. Inst. of RAS, 2025