О характеризации графов с числом эквивалентного разбиения не выше трех в классе хордальных графов

Abstract

It is proved that the class P of graphs with the equivalence partition number at most 3 cannot be characterized by means of a finite list of forbidden induced subgraphs in the class of chordal graphs with the Krausz dimension at most 3. Such a finite characterization of the class P is obtained in the class of chordal graphs with diameter at most 2. Доказано, что в классе хордальных графов с краусовой размерностью не выше трех класс Р графов с числом эквивалентного разбиения не выше трех нельзя охарактеризовать посредством конечного списка запрещенных порожденных подграфов. Получена конечная характеризация в тех же терминах для класса Р в классе хордальных графов диаметра не выше двух.