Граф расщеплений

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф расщеплений (Split graph) — неориентированный граф G = (V,E), имеющий такое разбиение множества вершин V = S \cup K, что подграф G[S] пустой, а подграф G[K] полный.

Фолдеш и Хаммер (Foldes, Hammer) в 1977 г. доказали следующий критерий: Gграф расщеплений тогда и только тогда, когда G и \bar{G}хордальные графы.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980.