1-й сем-ДМ-слайды-ДГТУ / Графы, л.5-7 / раскрашивание графов
.docРаскрашивание графов.
При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро инцидентно вершинам разного цвета?
Х
Если G-K-раскрашиваемый, но не является (K-1)-раскрашиваемым, то назовем его K- хроматическим, а число K- хроматическим числом графа G и обозначим X(G).
Пример:
4- хроматический
К≥4- раскрашиваемый граф
Граф может иметь кратные ребра.
Ясно, что X( Kn )= n.
С другой стороны X(G)=1, если G-вполне несвязный граф. X(G)=2, если G- двудольный граф, отличный от вполне несвязного графа. Любое дерево, имеющее не менее двух вершин, является 2-хроматическим.
Теорема 1.Если наибольшая из степеней вершин графа G равна P, то граф (Р+1)- раскрашиваем.
Доказательство. По индукции. Пусть G-граф с n-вершинами. Если из него удалить производную вершину V вместе с инцидентными ей ребрами, то в оставшемся графе будет n-1 вершин, причем, степени вершин не превосходят Р. По предположению индукции этот граф (Р+1)- раскрашиваем => получается (Р+1)- раскраска для G, если окрасить вершину U цветом, отличным от тех, которыми окрашены смежные с ней вершины (а их не более чем Р).
Теорема 2. (Брукс) Пусть наибольшая из степеней вершин графа G равна Р. Тогда G-P-раскрашиваемый, за исключением тех случаев, когда
1) G содержит в качестве компоненты граф Kp+1
2) Р=2 и угол нечетной длины является компонентой G.
Теорема 3. Любой граф 5-раскрашиваем.
Гипотеза четырех красок. Всякий граф 4-раскрашиваем.
Известно, что а) всякий граф, имеющий менее 52 вершин, 4-раскрашиваем. б) любой, не содержащий треугольников граф, 3-раскрашиваем. (теорема Грега)
Усиление теоремы 1 =>
Теорема 4. Пусть G- простой связный граф, не являющийся полным ,если наибольшая из степеней его вершин равна Р(Р≥3), то Р- раскрашиваем.
Реберная раскраска.
Граф G- реберно K- раскрашиваем, если его ребра можно раскрасить K красками таким образом, что никакие два смежных ребра не окажутся одного цвета. Если граф G-реберно K-раскрашиваем, но не является реберно (K-1)-раскрашиваемым, то K-хроматическое число (хроматический класс или хроматический индекс) графа G.
X(G)=K.
X(G)=4
Ясно, что если наибольшая из степеней вершин графа G равна Р, то Xi(G)≥P
Теорема 5. (Визинг).Пусть в графе G, не имеющем петель, наибольшая из степеней вершин равна Р, тогда ρ≤Xl(b)≤Р=1.
Пример: известно, что Хl(Cn)=2, если n-четно, Хl(Cn)=3, если нечетно.
Теорема 6. Xl(Km,n)=P=max (m,n).
Хроматический класс любого двудольного графа равен Р.