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

Abstract

For any r ≥ 3, m ≥ 2, the existence of finite characterization of the class L of edge intersection graphs of hypergraphs with rank at most r and multiplicity at most m in terms of forbidden induced subgraphs in the class of split graphs is proved. It is shown that similar finite characterization of the graphs in, L r ≥ 3, m ≥ 2, does not exist in the class of all graphs. = Доказано, что для любых фиксированных чисел r ≥ 3, m ≥ 2 графы из класса L реберных графов гиперграфов ранга не выше r и кратности не выше m характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов. Показано, что подобной конечной характеризации для графов из, r ≥ 3, m ≥ 2, не существует в классе всех графов.