Критические графы

Если гипотеза четырех красок не верна, то должен существовать

наименьший 5-хрометический планарный граф. Такой граф G обладал бы тем свойством, что для любой его вершины и подграф G — v был бы

4-хроматическим. Таким образом, у нас есть естественный подход к возможному доказательству гипотезы четырех красок в ее обратной постановке. Отсюда возникает основная задача изучения таких 5-хроматических графов или, более общо, n-хроматических графов G, что x(G—v)=n—1 для любой вершины v графа G.

Следуя Дираку граф G назовем, критическим, если xr(G—v)< xr(G) для любой его вершины v; если при этом xr(G)=n, то граф G называется n-критическим. Очевидно, если G — критический граф, то хr(G—u) = xr(G)—1 для каждой его вершины v.

Ясно, что 1-критических графов нет. Единственный 2-критический граф — это К2, все 3-критические графы исчерпываются простыми циклами нечетной длины, n-критические графы для n> 4 еще не описаны.

Как правило, определить, является ли данный граф критическим, чрезвычайно трудно. Однако каждый n-хроматический граф, n > 2, содержит

n-критический подграф. Действительно, если Н — такой наименьший порожденный подграф графа G, что хr(H) = хr(G), то Н - критический граф.

Ясно, что каждый критический граф G связен. Далее, поскольку xr(G)=max хr(B), где максимум берется по всем блокам В графа G, то G должен быть блоком. Это одно из свойств, которыми обладают критические графы.

Теорема. Если G есть n-критический граф, то d(G)>n-1.

Приведем теперь результаты, связанные с удалением вершин.

Теорема. Критический граф нельзя разделить полным подграфом.

Следствие (а). Каждый разрез по вершинам критического графа содержит две несмежные вершины.

Каждый полный граф критический. Действительно, для U из V(Kp) справедливо равенство

xr(KP-U)=p - |U|. Для любого другого критического графа всегда, однако, можно удалить не менее 2 вершин, не уменьшая при этом хроматическое число более чем на 1. В самом деле, если S - произвольное независимое множество вершин n-критического графа, то x(G—S)=n-1. Отсюда в свою очередь вытекает, что если u и v — любые две вершины n-критического неполного графа G, то существуют такая его n-раскраска, что u и v принадлежат одному и тому же одноцветному классу, и такая его n-раскраска, что u и v принадлежат разным одноцветным классам.

В одном из направлений исследований свойства критических графов связывают с длинами циклов, в частности, окружения и обхвата. Если G есть

n-критический граф с р-вершинами и р<2п—1, то в силу теоремы и следствия (б) граф G гамильтонов. Дирак получил более общий результат.

Теорема. Если G есть n-критический граф, n> 3, то или G гамильтонов, или его окружение не меньше 2п—2.

Дирак предполагал, что каждый 4-критический граф гамильтонов. Однако Дж. и Л. Келли показали, что эта гипотеза неверна. Дирак также предполагал, что для любых m и n, n>3, существует достаточно большое значение р, при котором у всех n-критических графов, имеющих по крайней мере р вершин, окружение превосходит m. Дж. и Л. Келли подтвердили это. Из теоремы вытекает, что для любых m и n существует n-критический граф, обхват которого превосходит m.

Критический граф G может обладать еще одним свойством: xr(G—x) = xr(G)—1 для любого ребра х графа G. В этом случае граф G называется реберно-критическим; если xr(G)=n, то G называется n-реберно-критическим. Хотя каждый реберно-критический граф обязательно является критическим, обратное не верно. Например, граф G, представленный на рисунке является 4-критическим, но не реберно-критическим, поскольку xr(G—х)=4.

Таким образом, реберно-критические графы обладают всеми свойствами критических графов, но в некоторых случаях о первых графах можно сказать больше, чем о вторых.

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

n-реберно-критическим.