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 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¹(k) is polynomially solvable if k = 2 and is NP-complete if k = 3. The complexity of the recognition of graphs from L^m(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 L¹(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 L²(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 L^m(3) (for fixed m ≥ 2) exists in the class of split graphs. In particular, it follows that the problem of recognizing graphs from L^m(3), m ≥ 2 is polynomially solvable in the class of split graphs.