Введение
1 Граничные классы графов: значение и примеры 13
1.1 Некоторые обозначения и определения 13
1.1.1 Множества 13
1.1.2 Отношения 14
1.1.3 Графы и подграфы 14
1.1.4 Множества вершин и числовые характеристики 16
1.1.5 Классы графов 16
1.2 «Критические» наследственные классы графов 18
1.3 Расширение пределов справедливости теоремы В.Е. Алексеева . 22
1.4 Критерий граничности 26
1.5 Новые случаи граничности класса Т и его производных 27
1.5.1 Условия граничности классов Т и Т> 27
1.5.2 Множество задач на графах с граничными классами Т
и Т> континуальной мощности 29
1.5.3 Древесная ширина и кликовая ширина графов и их применение при установлении граничности классов Т и Т> . 34
1.5.4 Производные от Т классы и некоторые случаи их граничности 38
2 Относительные граничные системы и их свойства 40
2.1 Относительные граничные классы 40
2.2 Строение относительной граничной системы для ряда задач на графах 42
2.2.1 Критерий полноты множества относительных граничных классов 42
2.2.2 Относительные граничные системы из производных класса Т 42
2.2.3 Граничные классы графов для задач о списковом ранжировании относительно лесов 44
2.3 Факторизация решетки наследственных классов графов и ее свойства 57
2.3.1 Критерий принадлежности общему фактор-классу и «избыточные» классы эквивалентности 57
2.3.2 О независимости понятий минимального сложного, абсолютного граничного и относительного граничного классов графов 64
2.3.3 Об одном свойстве относительных граничных классов в задаче о наибольшем двудольном планарном подграфе 65
2.3.4 Подмножества относительных граничных систем и их свойства 67
3 Полиномиальная разрешимость задачи НМ для некоторых классов графов 71
3.1 Гипотеза В.Е. Алексеева и ее варианты 71
3.2 Гасширяющие операторы для задачи о независимом множестве 74
3.2.1 О НМ-расширяемости оператора {P^^C^^G} —> {Р^С^СоКг} 75
3.2.2 О НМ-расширяемости оператора {Р5,С$, Н} —> {P5,C5,Ho02lHKhp} 80
3.3 Полиномиальная разрешимость задачи НМ в классе планарных графов, не содержащих больших порожденных яблок 87
3.3.1 Разделяющие клики и С-блоки 87
3.3.2 Свойства планарных графов без больших порожденных звезд 87
3.3.3 Минорно безапексные графы большой древесной ширины 90
3.3.4 Доказательство основного результата первой части главы 91
3.4 Полиномиальная разрешимость задачи НМ в классе субкуби ческих планарных графов без порожденного подграфа Т 97
3.4.1 Вспомогательные результаты 97
3.4.2 Присоединенные циклы и их разрушение 99
3.4.3 Гармони и их разрушение 108
3.4.4 Основные результаты второй части главы 115
О задачах на графах с континуальными граничными системами 118
4.1 Некоторые результаты из количественной теории граничных классов и смежные с ними 118
4.2 Граничные классы графов для задач о 3-раскраске 119
4.3 Свойства подмножеств 3-РР-граничной системы 128
4.4 Граничные классы графов для задач о /с-раскраске 130
4.5 Сравнительный анализ граничных систем для задач о к-раскраске и о хроматическом числе и индексе 132
«Критические» классы графов для задачи о реберном списковом ранжировании 136
5.1 Краткое описание основных результатов пятой главы 136
5.2 Новые минимальные РСР-сложные случаи 137
5.2.1 О минимальной РСР-сложности класса графов Bat 137
5.2.2 О минимальной РСР-сложности классов графов Comb, Camomile и Clique 141
5.3 Новые РСР-граничные случаи 143
5.4 Полная классификация классов графов из некоторого семейства по вычислительной сложности задачи РСР и следствия из нее 144
5.4.1 Оценки количеств вершин, степеней вершин и диаметров графов из некоторых классов 145
5.4.2 О принадлежности каждого конечно определенного класса семейству Л 151
5.4.3 Критерий эффективной разрешимости задачи РСР в семействе Ж и следствия из него 154
6 Минимальные сложные классы графов 158
6.1 О задачах на графах без минимальных сложных случаев .158
6.2 Условия и примеры существования минимальных сложных классов графов 159
6.3 О связи и о независимости понятий минимального сложного и граничного классов графов 165
Литература 167
