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

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).

Keywords

• edge intersection graph of hypergraph
• forbidden induced subgraph
• characterization
• split graph