Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs
Abstract
A hypergraph is called k-chromatic if its vertex set can be partitioned into at most k pairwise disjoint subsets when each subset has no more than two common vertices with every edge of the hypergraph. The multiplicity of a pair of vertices in a hypergraph is the number of hypergraph edges containing the pair of vertices. The multiplicity of a hypergraph is the maximum multiplicity of the pairs of vertices. Let Lm(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 L1(k) is polynomially solvable if k = 2 and is NP-complete if k = 3. The complexity of the recognition of graphs from Lm(k) for fixed k ≥ 2 and m ≥ 2 is currently unknown.
A split graph is a graph whose vertices can be partitioned into a clique and an independent set. It is known that for any k ≥ 2 the graphs from L1(k) can be characterized by a finite list of forbidden induced subgraphs in the class of split graphs. It was earlier proved that there exists a finite characterization in terms of forbidden induced subgraphs for the graphs from L2(3) in the class of split graphs.
It is proved in the article that a finite characterization in terms of forbidden induced subgraphs for the graphs from Lm(3) (for fixed m ≥ 2) exists in the class of split graphs. In particular, it follows that the problem of recognizing graphs from Lm(3), m ≥ 2 is polynomially solvable in the class of split graphs.
About the Author
T. V. Lubasheva
Belarus State Economic University
Belarus
Belarus
Tatyana V. Lubasheva – Assistant.
26, Partizanski Avе., 220070, Minsk
References
1. Lubasheva T. V., Metelsky Yu. M. Kharakterizatsiya i raspoznavanie grafov peresecheniy ryober 3-khromaticheskikh gipergrafov kratnosti ne vyshe 2 v klasse rasscheplyaemykh grafov [Characterization and recognition of edge intersection graphs of 3-chromatic hypergraphs with multiplicity at most then 2 in the class of split graphs]. Zhurnal Belorusskogo gosudarstvennogo universiteta. Matematika. Informatika [Journal of the Belarussian State University. Mathematics and Informatics], 2017, no. 3, pp. 94-99 (in Russian).
2. Berge C. Hypergraphs. Combinatorics of Finite Sets. Amsterdam, New-York, Oxford, Tokyo, North-Holland, 1989, 528 p.
3. Tyshkevich R. I., Urbanovich O. P., Zverovich I. E. Matroidal decomposition of graph. Combinatorics and Graph Theory, 1989, vol. 25, pp. 195-205.
4. Tyshkevich R. I. , Urbanovich O. P. Graphy s matroidnym chislom 2 [Graphs with matroidal number 2]. Vestsi akademii navuk BSSR. Seryia fizika-matematychnykh navuk [Proceedings of the Academy of Sciences of BSSR. Physics and Mathematics Series], 1989, no. 3, pp. 13-17 (in Russian).
5. Metelsky Yu. M., Tyshkevich R. I. Peresecheniya matroidov i ryobernye gipergrafy [Matroid intersections and line hypergraphs]. Trudy Instituta matematiki Natsyonalnoi akademii nauk Belarusi [Proceedings of the Institute of Mathematics of the National Academy of Sciences of Belarus], 2005, vol. 13, no. 2, pp. 44-54 (in Russian).
6. Harary F., Holzmann C. Line graphs of bipartite graphs. Revista de la SociedadMatematica de Chile, 1974, vol. 1, pp. 19-22.
7. Tyishkevich R. I., Chernyak A. A. Kanonicheskoe razlozhenie grafa, opredelyaemogo stepenyami ego vershin [The canonical decomposition of a graph defined by the degrees of its vertices]. Vestsi akademii navuk BSSR. Seryia fizika-matematychnykh navuk [Proceedings of the Academy of Sciences of the BSSR. Physics and Mathematics Series], 1979, vol. 5, pp. 14-26 (in Russian).
8. Foldes S., Hammer P. L. Congressus numerantium. Winnipeg: Utilitas Math., 1977, vol. XIX, pp. 311-315.
9. Foldes S., Hammer P. L. Split graphs having Dilworth number two. Canadian Journal of Mathematics, 1977, vol. 29, iss. 3, pp. 666-672.
10. Babaitsev A. Yu., Tyshkevich R. I. Lineynaya razmernost rasscheplyaemykh grafov [Linear dimension of split graphs]. Vestsi Natsyyanalnai akademii navuk Belarusi. Seryia fizika-technichnych navuk [Proceedings of the National Academy of Sciences of Belarus. Physical-technical series], 1999, no. 1, pp. 112-115 (in Russian).
11. Eskov V. V., Tyishkevich R. I. K kharakterizatsii ryobernykh grafov lineynykh gipergrafov pri dopolnitelnykh ogranicheniyakh [On characterization of edge graphs of linear hypergraphs under additional constraints]. Vestsi Natsyyanal’nai akademii navuk Belarusi. Seryia fizika-technichnych navuk [Proceedings of the National Academy of Sciences of Belarus. Physical-technical series], 2001, no. 2, pp. 122-126 (in Russian).
12. Lubasheva T. V., Metelsky Yu. M. O konechnoy kharakterizuemosti grafov s ogranichennym chislom ekvivalentnogo razbieniya v klassakh polyarnykh grafov [About finite characterizability of graphs with a bounded number of equivalent decomposition in classes of polar graphs]. Trudy Instituta matematiki Natsyonal’noi akademii nauk Belarusi [Proceedings of the Institute of Mathematics of the National Academy of Sciences of Belarus], 2011, vol. 19, no. 1, pp. 85-91 (in Russian).
13. Lubasheva T. V., Metelsky Yu. M. Kharakterizatsiya grafov s ogranichennym sverkhu chislom ekvivalentnogo razbieniya v klasse U-rasscheplyaemykh grafov [Characterization of graphs with upper bound on the number of equivalent decomposition in the class of U-split graphs]. Trudy Instituta matematiki Natsyonal’noi akademii nauk Belarusi [Proceedings of the Institute of Mathematics ofthe National Academy ofSciences of Belarus], 2007, vol. 15, no. 1, pp. 91-97 (in Russian).
14. Tyishkevich R. I., Chernyak A. A. Dekompozitsiya grafov [Decomposition of graphs]. Kibernetika [Cybernetics], 1985, no. 2, pp. 67-74 (in Russian).
Review
For citations:
Lubasheva T.V. Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs. Informatics. 2018;15(4):102-108. (In Russ.)
Views: 596
Email this article 