Cтраница 2
Квазиполный граф квазиплотности К представляет собой граф GK F, [ /, обладающий следующим свойством, которое не выполняется ни для одного его частичного графа: хроматическое число графа GK равно К. Из определения квазиполного графа следует, что наличие на графе квазиполного графа квазиплотности К не позволяет его раскрасить в К красок. С другой стороны, отсутствие на графе квазиполных графов квазиплотности К делает его / - раскрашиваемым. Таким образом, квазиполные графы являются запрещенными фигурами раскраски вершин графа. Существует только один квазиполный граф квазиплотности два - это граф, состоящий из двух смежных вершин. Для случая К 3 квазиполными графами являются циклы нечетной длины. [16]
Процедуры порождения квазиполных графов GK, где К Ъ разбивают на два класса. [17]
Утверждение 2.9 позволяет определить минимальные значения мощности носителя Кмия и сигнатуры ( 7МИЯ квазиполного графа с заданными значениями порядка и плотности. Определим экстремальные значения FMHH и С / мин для квазиполных графов с четной плотностью. [18]
Теорема 2.1. Пусть C7Kl Fb U и GK2 ( V2, [ / 2 - квазиполные графы квазиплотности К. Тогда для любой вершины VjeVi и любого ребра ( vj vl) eU2 справедливо следующее утверждение: при замещении вершины vt графом G GK2 ( tb, y () путем замены каждого ребра графа GKl вида ( vr, vt) ребром ( vr, Vj) либо ребром ( vr, v) такой, что множества ребер вида ( vr, v и вида ( vr, vt) одновременно непустые, получается квазиполный граф квазишютности К. [19]
Среди множества пар несмежных вершин графа G рассмотрим [2. 9] те пары, которые должны быть обязательно соцветны при любой минимальной раскраске графа. Наличие таких пар вершин определяется присутствием на графе подграфов специального вида, представляющих собой согласно лемме 2.1 квазиполные графы без одного ребра. Поскольку удаление любого ребра квазиполного графа, с одной стороны, устраняет все циклы, проходящие через это ребро, а с другой стороны, делает вершины, коинцидентные данному ребру, соцветными, получаем непосредственную связь между распределением порожденных циклов нечетной длины на графе и соцветностью его вершин. [20]
Замыкающий слой для множества вершин У ( р) образуется добавлением вершины г., смежной с каждой вершиной из - ( с одной из вершин из каждого подмножества Кр. Кроме того, для множества Fp замыкающий слой образуется либо добавлением ребра, соединяющего две вершины из одного подмножества Кр. Данные графы получены из полного графа G4 с помощью генератора квазиполных графов, в основе которого лежат рассмотренные процедуры. [21]
G такая, что вершины г - и г, окрашены в разные краски. В результате получим правильную раскраску графа GK, которая совпадает с минимальной раскраской его частичного графа и, что противоречит определению квазиполного графа. [22]