Geodesic
Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs
Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 91-97 
T. V. Lubasheva; Yu. M. Metelsky. Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs. Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 91-97. http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a9/
@article{TIMB_2007_15_1_a9,
     author = {T. V. Lubasheva and Yu. M. Metelsky},
     title = {Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs},
     journal = {Trudy Instituta matematiki},
     pages = {91--97},
     year = {2007},
     volume = {15},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a9/}
}
TY  - JOUR
AU  - T. V. Lubasheva
AU  - Yu. M. Metelsky
TI  - Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs
JO  - Trudy Instituta matematiki
PY  - 2007
SP  - 91
EP  - 97
VL  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a9/
LA  - ru
ID  - TIMB_2007_15_1_a9
ER  - 
%0 Journal Article
%A T. V. Lubasheva
%A Yu. M. Metelsky
%T Characterization of the graphs with bounded above equivalence partition number in the class of $\mathcal U$-split graphs
%J Trudy Instituta matematiki
%D 2007
%P 91-97
%V 15
%N 1
%U http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a9/
%G ru
%F TIMB_2007_15_1_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Behrendt G., “Semicomplete factorization of graphs”, Bull. London Soc., 20:1 (1988), 11–15 | DOI | MR | Zbl

[2] Babaitsev A.Yu., Tyshkevich R.I., “Lineinaya razmernost rasscheplyaemykh grafov”, Vestsi NAN Belarusi. Ser. fiz.-mat. navuk, 1999, no. 1, 112–115 | MR

[3] Babaitsev A.Yu., “Silnaya gipoteza Berzha dlya rebernykh grafov lineinykh 3-raskrashivaemykh gipergrafov”, Dokl. NAN Belarusi, 42:1 (1998), 34–37 | MR | Zbl

[4] Tyshkevich R.I., Levin A.G., Rebernye grafy i peresecheniya matroidov, Preprint No 23, ITK AN BSSR, Minsk, 1990

[5] Tyshkevich R.I., Urbanovich O.P., “Grafy s matroidnym chislom 2”, Vestsi AN BSSR. Ser. fiz.-mat. navuk, 1989, no. 3, 13–17 | MR | Zbl

[6] Földes S., Hammer P.L., “Split graphs”, Proceedings of the 8-th South-East Conf. of Combinatorics, Graph Theory and Computing, Congress. Numerantium, 19, 1977, 311–315 | MR

[7] Tyshkevich R., “Decomposition theorem and unigraphs”, Discrete Math., 220:1–3 (2000), 201–238 | DOI | MR | Zbl

[8] Skums P.V., Suzdal S.V., Tyshkevich R.I., “Ob odnom rasshirenii klassa rasscheplyaemykh grafov”, Vestsi NAN Belarusi. Ser. fiz.-mat. navuk, 2005, no. 4, 65–71 | MR

[9] Tyshkevich R.I., “Kanonicheskoe razlozhenie grafa”, Dokl. AN BSSR, 24:8 (1980), 677–679 | MR | Zbl