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

Пусть $L^{m}k$ обозначает класс графов пересечений ребер $k$-хроматических гиперграфов кратности не выше $m$. Известно, что задача распознавания графов из $L^{1}(k)$ полиномиально разрешима при $k=2$ и является $NP$-полной при $k=3$. Также известно, что для любого $k\geq 2$ графы из $L^{1}k$ характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов. Вопрос о сложности распознавания графов из $L^{m}k$ при фиксированных $k\geq 2$ и $m\geq 2$ в настоящее время остается открытым. Здесь доказано, что для графов из $L^{2}(3)$ существует конечная характеризация в терминах запрещенных порожденных подграфов в классе расщепляемых графов. Отсюда, в частности, вытекает полиномиальная разрешимость задачи распознавания $G\in L^{2}(3)$ в классе расщепляемых графов. Результаты получены на основе доказанной в работе характеризации графов из $L^{2}(3)$ в терминах степеней вершин в одном из подклассов расщепляемых графов. В свою очередь, указанная характеризация получена с помощью известного описания графов из $L^{m}(k)$ в терминах покрытий кликами, а также доказанной в работе леммы о большой клике, уточняющей взаимное расположение клик в графе из $L^{m}(k)$.