Geodesic
Characterization and recognition of edge intersection graphs of $3$-chromatic hypergraphs with multiplicity at most than two in the class of split graphs
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2017), pp. 94-99.

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

Let $L^{m}k$ denote the class of edge intersection graphs of $k$-chromatic hypergraphs with multiplicity at most $m$. It is known that the problem of recognizing graphs from $L^{1}(k)$ is polynomially solvable if $k=2$ and is $NP$-complete if $k=3$. It is also known that for any $k\geq 2$ the graphs from $L^{1}k$ can be characterized by a finite list of forbidden induced subgraphs in the class of split graphs. The question of the complexity of recognizing graphs from $L^{m}k$ for fixed $k\geq 2$ and $m\geq 2$ remains open. Here it is proved that there exists a finite characterization in terms of forbidden induced subgraphs for the graphs from $L^{2}(3)$ in the class of split graphs. In particular, it follows that the problem of recognizing graphs from $G\in L^{2}(3)$ is polynomially solvable in the class of split graphs. The results are obtained on the basis of proven here characterization of the graphs from $L^{2}(3)$ in terms of vertex degrees in one of the subclasses of split graphs. In turn, this characterization is obtained using the well-known description of graphs from $L^{m}(k)$ by means of clique coverings and proven here Lemma on large clique, specifying the mutual location of cliques in the graph from $L^{m}(k)$.
Keywords: edge intersection graph of hypergraph; forbidden induced subgraph; characterization; split graph. 
@article{BGUMI_2017_3_a9,
     author = {T. V. Lubasheva and Yu. M. Metelsky},
     title = {Characterization and recognition of edge intersection graphs of $3$-chromatic hypergraphs with multiplicity at most than two in the class of split graphs},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {94--99},
     publisher = {mathdoc},
     volume = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2017_3_a9/}
}
TY  - JOUR
AU  - T. V. Lubasheva
AU  - Yu. M. Metelsky
TI  - Characterization and recognition of edge intersection graphs of $3$-chromatic hypergraphs with multiplicity at most than two in the class of split graphs
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2017
SP  - 94
EP  - 99
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2017_3_a9/
LA  - ru
ID  - BGUMI_2017_3_a9
ER  - 
%0 Journal Article
%A T. V. Lubasheva
%A Yu. M. Metelsky
%T Characterization and recognition of edge intersection graphs of $3$-chromatic hypergraphs with multiplicity at most than two in the class of split graphs
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2017
%P 94-99
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2017_3_a9/
%G ru
%F BGUMI_2017_3_a9
T. V. Lubasheva; Yu. M. Metelsky. Characterization and recognition of edge intersection graphs of $3$-chromatic hypergraphs with multiplicity at most than two in the class of split graphs. Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2017), pp. 94-99. http://geodesic.mathdoc.fr/item/BGUMI_2017_3_a9/

[1] C. Berge, “Hypergraphs. Combinatorics of finite sets”, Amsterdam: North-Holland, 1989 | MR | Zbl

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

[3] Yu. M. Metelskii, R. I. Tyshkevich, “Peresecheniya matroidov i rebernye gipergrafy”, Tr. In-ta matematiki NAN Belarusi, 13, # 2 (2005), 44–54

[4] F. Harary, C. Holzmann, “Line graphs of bipartite graphs”, Rev. Soc. Mat. Chile, 1 (1974), 19–20

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