Краусова декомпозиция в специальных классах расщепляемых графов

Abstract

The criterion of belonging of graphs of the form Kn-EKm to the class of edge intersection graphs of linear k-uniform hypergraphs is obtained. This criterion allows to obtain an explicit expression for krausz dimension of such graphs. For split graphs with high enough vertex degrees the analogue of the classical Whitney theorem is proved. Получен критерий принадлежности классу графов пересечений ребер линейных k-униформных гиперграфов для графов вида Кn-ЕКm, позволяющий получить явное выражение для краусовой размерности таких графов. Для расщепляемых графов с достаточно большими степенями вершин доказан аналог классической теоремы Уитни.