Характеризация и распознавание графов пересечений ребер трихроматических гиперграфов ограниченной кратности в классе расщепляемых графов
Аннотация
Гиперграф, множество вершин которого можно разбить не более чем на к попарно непересекающихся подмножеств, каждое из которых имеет не более одной общей вершины с любым ребром гиперграфа, называется к-хроматическим. Кратность пары вершин гиперграфа - это число его ребер, содержащих обе вершины пары, тогда кратность гиперграфа - это максимальная кратность пар его вершин. Пусть Lm(k) обозначает класс графов пересечений ребер к-хроматических гиперграфов кратности не выше m. Задача распознавания графов из L1(k) полиномиально разрешима при к = 2 и является NP-полной при к = 3. Вопрос о сложности распознавания графов из Lm(k) при фиксированных к ≥ 2 и m ≥ 2 в настоящее время остается открытым.
Граф называется расщепляемым, если множество его вершин можно разбить на два непересекающихся подмножества, одно из которых является кликой, а другое - независимым множеством вершин. Для любого к ≥ 2 графы из L1(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов.
Ранее было доказано [1], что для графов из L2(3) существует конечная характеризация в терминах запрещенных порожденных подграфов в классе расщепляемых графов. В настоящей работе этот результат обобщен на класс Lm(3), где фиксированное m ≥ 2. Важным следствием основного результата работы является полиномиальная разрешимость задачи распознавания Gϵ Lm(3) в классе расщепляемых графов.
Для цитирования:
Лубашева Т.В. Характеризация и распознавание графов пересечений ребер трихроматических гиперграфов ограниченной кратности в классе расщепляемых графов. Информатика. 2018;15(4):102-108.
For citation:
Lubasheva T.V. Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs. Informatics. 2018;15(4):102-108. (In Russ.)
Просмотров: 629
Послать статью по эл. почте 