Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs

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

Full description

Saved in:
Bibliographic Details
Main Author: T. V. Lubasheva
Format: Article
Language:Russian
Published: National Academy of Sciences of Belarus, the United Institute of Informatics Problems 2018-12-01
Series:Informatika
Subjects:
Online Access:https://inf.grid.by/jour/article/view/443
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1816-0301