Characterization and recognition of edge intersection graphs of 3-chromatic hypergraphs with multiplicity at most than two in the class of split graphs

  • Tatiana V. Lubasheva Belarus State Economic University, 26 Partyzanski Аvenue, Minsk 220070, Belarus
  • Yury M. Metelsky Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

Abstract

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. It is also 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. The question of the complexity of recognizing graphs from Lm(k) for fixed k ≥ 2 and m ≥ 2 remains open. Here it is 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. In particular, it follows that the problem of recognizing graphs from L2(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 L2(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 Lm(k) by means of clique coverings and proven here Lemma on large clique, specifying the mutual location of cliques in the graph from Lm(k).

Author Biographies

Tatiana V. Lubasheva, Belarus State Economic University, 26 Partyzanski Аvenue, Minsk 220070, Belarus

assistant at the department of economic informatics, faculty of management

Yury M. Metelsky, Belarusian State University, Niezaliežnasci Avenue, 4, 220030, Minsk, Belarus

PhD (physics and mathematics), docent; associate professor at the department of mathematical cybernetics, faculty of mechanics and mathematics

References

  1. Berge C. Hypergraphs. Combinatorics of finite sets. Amsterdam : North-Holland, 1989.
  2. Tyshkevich R. I., Urbanovich O. P. [Graphs with matroidal number 2]. Vesti Akadjemii navuk BSSR. Ser. fiz.-mat. navuk. 1989. No. 3. P. 13–17 (in Russ.).
  3. Metelsky Yu. M., Tyshkevich R. I. [Matroid intersections and line hypergraphs]. Tr. Inst. mat. Natsionalʼnoi Akad. nauk Belarusi. 2005. Vol. 13, No. 2. P. 44 –54 (in Russ.).
  4. Harary F., Holzmann C. Line graphs of bipartite graphs. Rev. Soc. Mat. Chile. 1974. Vol. 1. P. 19–20.
  5. Babaitsev A. Yu., Tyshkevich R. I. [Linear dimension of split graphs]. Vesti Nacyjanalʼaj Akadjemii navuk Belarusi. Ser. fiz.-mat. navuk. 1999. No. 1. P. 112–115 (in Russ.).
Published
2018-02-14
Keywords: edge intersection graph of hypergraph, forbidden induced subgraph, characterization, split graph
How to Cite
Lubasheva, T. V., & Metelsky, Y. M. (2018). 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, 3, 94-99. Retrieved from https://journals.bsu.by/index.php/mathematics/article/view/762
Issue
No 3 (2017): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)