Характеризация и распознавание графов пересечений ребер 3-хроматических гиперграфов кратности не выше двух в классе расщепляемых графов - Лубашева, Татьяна Владимировна; Метельский, Юрий Михайлович (Журнал Белорусского государственного университета. Математика. Информатика, 2018)
Пусть Lm(k) обозначает класс графов пересечений ребер k-хроматических гиперграфов кратности не выше m. Известно, что задача распознавания графов из L1(k) полиномиально разрешима при k = 2 и является NP-полной при k = 3. Также известно, что для любого k ≥ 2 графы из L1(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов. Вопрос о сложности распознавания графов из Lm(k) при фиксированных k ≥ 2 и m ≥ 2 в настоящее время остается открытым. Здесь доказано, что для графов из L2(3) существует конечная характеризация в  терминах запрещенных порожденных подграфов в классе расщепляемых графов. Отсюда, в частности, вытекает полиномиальная разрешимость задачи распознавания G ∈L2(3) в классе расщеп ляемых графов. Результаты получены на основе доказанной в работе характеризации графов из L2(3) в терминах степеней вершин в одном из подклассов расщепляемых графов. В свою очередь, указанная характеризация получена с помощью известного описания графов из Lm(k) в терминах покрытий кликами, а также доказанной в работе леммы о большой клике, уточняющей взаимное расположение клик в графе из Lm(k).
Keywords: граф пересечений ребер гиперграфа; запрещенный порожденный подграф; характеризация; расщепляемый граф