Лубашева Татьяна Владимировна – ассистент.
Пр. Партизанский, 26, 220070, Минск
Tatyana V. Lubasheva – Assistant.
26, Partizanski Avе., 220070, Minsk
Гиперграф, множество вершин которого можно разбить не более чем на к попарно непересекающихся подмножеств, каждое из которых имеет не более одной общей вершины с любым ребром гиперграфа, называется к-хроматическим. Кратность пары вершин гиперграфа - это число его ребер, содержащих обе вершины пары, тогда кратность гиперграфа - это максимальная кратность пар его вершин. Пусть Lm(k) обозначает класс графов пересечений ребер к-хроматических гиперграфов кратности не выше m. Задача распознавания графов из L1(k) полиномиально разрешима при к = 2 и является NP-полной при к = 3. Вопрос о сложности распознавания графов из Lm(k) при фиксированных к ≥ 2 и m ≥ 2 в настоящее время остается открытым.
Граф называется расщепляемым, если множество его вершин можно разбить на два непересекающихся подмножества, одно из которых является кликой, а другое - независимым множеством вершин. Для любого к ≥ 2 графы из L1(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов.
Ранее было доказано [
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.
The authors declare that there are no conflicts of interest present.