Пусть G – двусвязный граф на n вершинах такой, что каждое его двухэлементное разделяющее множество разбивает G не более чем на 3 части, а n1+n2+n3=n. В работе доказано, что существует разбиение множества вершин графа G на такие непересекающиеся подмножества V1, V2, V3, что |Vi|=ni и индуцированный подграф G(Vi) связен для каждого i. Библ. – 9 назв.
Язык оригиналарусский
Страницы (с-по)26-47
ЖурналЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
Том464
СостояниеОпубликовано - 2017

    Области исследований

  • двусвязный граф, разбиение, теорема Дьори–Ловаса

ID: 51928112