*** 1.) Вершинная раскраска графа. ***


Пусть дан граф G = (X,E) – связный граф.

• Определение №1: ( Вершинная раскраска )
Отображение f: X(G)→ {1, 2,…, k} называется вершинной раскраской графа G.


• Определение №2: ( Правильная вершинная раскраска)
Вершинная раскраска называется правильной если для любых 2-ух смежных вершин  f(u) ≠ f(v).
f(u), f(v) – цвета вершин.

Очевидно, что при     правильной раскраске, в общем случае, возможно использование менее чем k различных цветов.
Если для графа G существует правильная раскраска k-цветами, говорим, что граф G
k – раскрашиваемый.

• Определение №3:             ( Хроматическое число )
Наименьшее значение k, при котором существует правильная раскраска вершин графа, называется хроматическим числом графа G.
        Обозначается:     χ(G).


*** 2.) Оценки Хроматического Числа графа. ***

• Теорема №1:
Пусть Ģ - семейство всех порожденных подграфов графа G = (X,E)
Для любого графа G верно нер-во:
χ(G) ≤ 1 + max δ(H) , H € Ģ
где δ(H) = min d(X) , X € H
• Следствие:
для любого графа G верно нер-во χ(G) ≤ 1 + Δ(G)
 
• Теорема №2: ( Теорема Брукса )
Для связного неполного графа G, в котором Δ(G) ≥ 3 верно нер-во:
χ(G) ≤ Δ(G)

• Теорема №3:
Для любого графа G верны нер-ва:
n/α_0 ≤ χ(G) ≤ n - α_0 + 1 , где α_0 - число независимости графа


*** 3.) Реберная раскраска графов. ***

Пусть дан граф G=(X,E) – связный граф.


• Определение №1: ( Реберная раскраска )

Отображение g: E→ {1, 2,…, k} называется реберной раскраской графа G.


• Определение №2: ( Правильная реберная  раскраска)
Реберная раскраска называется правильной если любые 2 смежные ребра получают разные цвета в указанной раскраске.


• Определение №3: ( Хроматический индекс )
Минимальное количество красок в правильной реберной раскраске графа называется хроматическим индексом графа G.
        Обозначается:     χ’(G).

• Определение №4: ( Реберный граф )
Граф, в котором каждая в-на соответствует некоторому ребру графа G и в котором 2 в-ны смежны <=> когда смежны соответствующие ребра графа G наз-ся реберным графом графа G.
        Обозначается:     L(G).

Очевидно, что χ’(G) = χ(L(G))