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
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},
year = {2017},
volume = {3},
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 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 %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