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

Аннотация

Пусть L^m(k) обозначает класс графов пересечений ребер k-хроматических гиперграфов кратности не выше m. Известно, что задача распознавания графов из L¹(k) полиномиально разрешима при k = 2 и является NP-полной при k = 3. Также известно, что для любого k ≥ 2 графы из L¹(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов. Вопрос о сложности распознавания графов из L^m(k) при фиксированных k ≥ 2 и m ≥ 2 в настоящее время остается открытым. Здесь доказано, что для графов из _L²(³) существует конечная характеризация в  терминах запрещенных порожденных подграфов в классе расщепляемых графов. Отсюда, в частности, вытекает полиномиальная разрешимость задачи распознавания G ∈L²(³) в классе расщеп ляемых графов. Результаты получены на основе доказанной в работе характеризации графов из _L²(³) в терминах степеней вершин в одном из подклассов расщепляемых графов. В свою очередь, указанная характеризация получена с помощью известного описания графов из L^m(k) в терминах покрытий кликами, а также доказанной в работе леммы о большой клике, уточняющей взаимное расположение клик в графе из L^m(k).