Характеризация и распознавание графов пересечений ребер трихроматических гиперграфов ограниченной кратности в классе расщепляемых графов

Гиперграф, множество вершин которого можно разбить не более чем на к попарно непересекающихся подмножеств, каждое из которых имеет не более одной общей вершины с любым ребром гиперграфа, называется к-хроматическим. Кратность пары вершин гиперграфа - это число его ребер, содержащих обе вершины пары, тогда кратность гиперграфа - это максимальная кратность пар его вершин. Пусть L^m(k) обозначает класс графов пересечений ребер к-хроматических гиперграфов кратности не выше m. Задача распознавания графов из L¹(k) полиномиально разрешима при к = 2 и является NP-полной при к = 3. Вопрос о сложности распознавания графов из L^m(k) при фиксированных к ≥ 2 и m ≥ 2 в настоящее время остается открытым.

Граф называется расщепляемым, если множество его вершин можно разбить на два непересекающихся подмножества, одно из которых является кликой, а другое - независимым множеством вершин. Для любого к ≥ 2 графы из L¹(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов.

Ранее было доказано [1], что для графов из L²(3) существует конечная характеризация в терминах запрещенных порожденных подграфов в классе расщепляемых графов. В настоящей работе этот результат обобщен на класс L^m(3), где фиксированное m ≥ 2. Важным следствием основного результата работы является полиномиальная разрешимость задачи распознавания Gϵ L^m(3) в классе расщепляемых графов.

1. Лубашева, Т. В. Характеризация и распознавание графов пересечений ребер 3-хроматических гиперграфов кратности не выше 2 в классе расщепляемых графов / Т. В. Лубашева, Ю. М. Метельский // Журнал Бел. гос. ун-та. Математика. Информатика. - 2017. - № 3. - С. 94-99.

2. Berge, C. Hypergraphs. Combinatorics of Finite Sets / C. Berge. - Amsterdam, New-York, Oxford, Tokyo : North-Holland, 1989. - 528 p.

3. Tyshkevich, R. I. Matroidal decomposition of graph / R. I. Tyshkevich, O. P. Urbanovich, I. E. Zverovich // Combinatorics and Graph Theory. - 1989. - Vol. 25. - P. 195-205.

4. Тышкевич, Р. И. Графы с матроидным числом 2 / Р. И. Тышкевич, О. П. Урбанович // Весщ АН БССР. Cер. фгз.-мат. навук. - 1989. - № 3. - C. 13-17.

5. Метельский, Ю. М. Пересечения матроидов и реберные гиперграфы / Ю. М. Метельский, Р. И. Тышкевич // Тр. Ин-та математики НАН Беларуси. - 2005. - Т. 13, № 2. - C. 44-54.

6. Harary, F. Line graphs of bipartite graphs / F. Harary, C. Holzmann // Rev. Soc. Mat. Chile. - 1974. - Vol. 1. -P. 19-22.

7. Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Известия АН БССР. Сер. физ.-мат. наук. - 1979. - Т. 5. - C. 14-26.

8. Foldes, S. Congressus numerantium / S. Foldes, P. L. Hammer // Winnipeg: Utilitas Math. - 1977. - Vol. XIX. -P. 311-315.

9. Foldes, S. Split graphs having Dilworth number two / S. Foldes, P. L. Hammer // Canadian Journal of Mathematics. -1977. - Vol. 29, iss. 3. - Р. 666-672.

10. Бабайцев, А. Ю. Линейная размерность расщепляемых графов / А. Ю. Бабайцев, Р. И. Тышкевич // Вес. Нац. акад. навук Беларуси Сер. фгз.-тэхн. навук. - 1999. - № 1. - C. 112-115.

11. Еськов, В. В. К характеризации реберных графов линейных гиперграфов при дополнительных ограничениях / В. В. Еськов, Р. И. Тышкевич // Вес. Нац. акад. навук Беларуси Сер. фгз.-тэхн. навук. - 2001. - № 2. -C. 122-126.

12. Лубашева, Т. В. О конечной характеризуемости графов с ограниченным числом эквивалентного разбиения в классах полярных графов / Т. В. Лубашева, Ю. М. Метельский // Тр. Ин-та математики НАН Беларуси. - 2011. -Т. 19, № 1. - С. 85-91.

13. Лубашева, Т. В. Характеризация графов с ограниченным сверху числом эквивалентного разбиения в классе U-расщепляемых графов / Т. В. Лубашева, Ю. М. Метельский // Тр. Ин-та математики НАН Беларуси. -2007. - Т. 15, № 1. - С. 91-97.

14. Тышкевич, Р. И. Декомпозиция графов / Р. И. Тышкевич, А. А. Черняк // Кибернетика. - 1985. - № 2. -C. 67-74.