Хроматическое число

Пусть граф G петель, тогда G – K – раскрашиваемый, если каждой его вершине можно приписать один из К цветов, так чтобы никакие 2 смежные вершины не оказались одного цвета.

Если G – К – раскрашиваемый, но не является (К-1)-раскрашиваемым, то назовем его К - хроматическим, а число К – хроматическим числом графа G и обозначим Х (G)

Пример: ρ

 

 

а в а

 

 

б

4 – хроматический и К≥4 – раскрашиваемый граф

Граф может иметь кратные ребра. Ясно, что Х( К п)=п

С другой стороны Х(6)=1, если G – вполне несвязный граф. Х(6)=2, если G – двудольный граф, отличный от вполне несвязного графа. Любое дерево, имеющее не менее 2-х вершин, является2-хроматическим.

Теорема 1:

Если наибольшая из степеней вершин графа G равна Р, то граф (ρ+1) – раскрашиваем

Док-во. По индукции. Пусть 6 – граф с п – вершинами. Если из него удалить производную вершину υ вместе с инцидентными ей ребрами, что в оставшемся графе будет и-1 вершин, причем, степени вершин не превосходят ρ. По предположению индукции этот граф (ρ+1) – раскрашиваем получается (ρ+1) – раскраска для G, если окрасить вершину υ цветом, отличные с ней вершины ( а их не более чем ρ).

Теорема 2:

(Брукс). Пусть наибольшая из степеней вершин графа G равна Р. Тогда G –P раскрашиваемый, за исключением тех случаев, когда:

1) G содержит в качестве компонента граф Кρ+1

2) Ρ=2 и цикл нечетной длин является компонент G

Теорема 3:

Любой планарный граф 5-раскрашиваем.

Гипотеза 4-х красок. Всякий планарный граф 4-раскрашиваем. Известно,

а) что всякий планарный граф, имеющий менее 52 вершин, 4-раскрашиваем

б) любой, не содержащий треугольников планарный граф 3-раскрашиваем. (теория Грега)

Теорема 4:

Пусть G-простой связный граф, не являющийся полным, если наибольшая из степеней его вершин равна ρ (ρ≥3), то он ρ-раскрашиваем.