Неравенства за броя на върховете на графи без триъгълници и с дадено хроматично число

Ако един граф G съдържа k–клика, тогава χ(G)≥k. Обратното, разбира се, не е вярно. Петоъгълникът C₅ например има хроматично число 3, но не съдържа триъгълници. Все пак изглежда доста вероятно, че ако един граф има хроматично число, той не може да има много малко кликово число и в частност ще съдържа триъгълници. Това обаче не е вярно. Оказва се, че за всяко естествено число k има граф G_k с хроматично число k, който не съдържа триъгълници.

Ясно е, че G₁ е графът с един връх K₁, G₂=K₂, а за G₃ можем да вземем C₅.

Лесно ще докажем следното:

Да разгледаме случая, когато d(G)=2 (ако d(G)≤1, χ(G)≤2). Съгласно предложение 3 G съдържа C_2r+1 за някое r. Тъй като G не съдържа C₃ и броят на върховете на G е най-много пет, то G трябва да съдържа C₅. Но тогава G ще съвпадне с C₅(защото иначе ще излезе, че d(G)>2).

Остана да се разгледа случая, когато d(G)=3. Възможността d(G)≥4 веднага се отхвърля. Нека d(G)=3 и v₁ е връх с d(v₁)=3, а v₂, v₃, v₄ са съседите му. Никой два от тях не са съседни, понеже в G няма триъгълници. Ще оцветим тогава v₂, v₃ и v₄ в един и същ цвят, а v₁ и останалия връх, на G (ако има такъв) ще оцветим също еднакво (тъй като не са съседни). Получаваме върхово 2-оцветяване на G.

Полученото противоречие завършва доказателството на предложение 4.

той е изобразен на фигура 1.

Графът G₄ има единадесет върха. Да докажем отначало, че G₄ не съдържа триъгълници. Наистина няма триъгълници с три върха от C₅. Очевидно няма и триъгълници с връх w. Ако допуснем, че все пак в G₄ има триъгълник, той трябва да е от вида [, ,], където са различни. Но тогава [v_i, ,] е също триъгълник на G₄, трите върха на който са от C₅. Полученото противоречие, показва, че в G₄ няма триъгълници.

Ще докажем, че χ(G₄)=4. Преди всичко съвсем лесно се вижда, че χ(G₄)≤4. Наистина да вземем върхово 3-оцветяване на C₅, да оцветим върховете в четвърти цвят, а w – в някой от първите три цвята. По такъв начин получаваме върхово 4-оцветяване на G₄.

Да допуснем сега, че χ(G₄)<4 и нека γ е 3-оцветяване на G₄. С γ(a) да означим цвета на произволен връх a на G₄. Тъй като са съседи на w, то γ()≠γ(w). Ще променим оцветяването γ във всички върхове v_i, за които γ(v_i)=γ(w), по следния начин: ако γ(v_i)=γ(w), полагаме δ(v_i)=γ(). За останалите върхове оставаме оцветяването γ, т.е. ако γ()≠γ(w), полагаме δ()=γ().

По такъв начин всеки връх има цвят δ(v_k), различен от γ(w). Ще докажем, че ако v_i и v_j са съседни върхове, тогава δ(v_i)≠δ(v_j). Това е очевидно, когато γ(v_i)≠γ(w) и γ(v_j)≠γ(w), защото тогава δ(v_i)=γ(v_j), δ(v_j)=γ(v_j) и γ(v_i)≠γ(v_j). Нека сега γ(v_i)=γ(w). Тъй като γ(v_i)≠γ(v_j), то γ(v_j)≠γ(w) и следователно δ(v_j)=γ(v_j). От дефиницията на оцветяването δ следва, че δ(v_i)=γ(u_i). Тъй като v_i и v_j са съседни, то u_i и v_j са съседни и следователно γ(u_i)≠γ(v_j), т.е. δ(v_i)≠δ(v_j).

Дефинирахме оцветяване δ в два цвята (различни от γ (w)) на върховете на C₅ и доказахме, че δ е върхово 2-оцветяване на C₅.

Полученото противоречие отхвърля допускането, че χ(G₄)<4.

Доказахме, че χ(G₄)=4.

Ако използваме графа G₄, тъй както използвахме в горните разсъждения графа C₅, ще можем да построим граф (с 2.11+1=23 върха), който няма триъгълници и има хроматично число 5.

Изобщо нека G е граф с върхове v₁, v₂,....,v_n, който не съдържа триъгълници. Ще въведем нови върхове u₁, u₂,...u_n и w. Всеки връх u_i ще съединим с ребро с кой да е връх v_j, съседен на v_i. Върхът w ще съединим с ребра с всички върхове u_i.

По такъв начин получаваме граф .

Както по-горе се доказва.

Теорема 4. и χ()=χ(G)+1.

От факта, че C₅ не съдържа триъгълници и χ(C₅)=3, както и от теорема 4, следва

Да означим с m(k) най-малкото n, за което съществува граф G с n върха, cl(G)=2 и χ(G)=k. Функцията m(k) е дефинирана за всяко естествено k, k≥2. Очевидно m(2)=2 и съгласно предложение 4 m(3)=5.

От теорема 4 очевидно следва

Следствие 4. .

От m(k+1)≤2m(k)+1 следва, че m(k+1)≤2(m(k)+1). Да положим f(k)=m(k)+1, k=2,3,.... Имаме f(k+1)≤2f(k), като положим k=2,3,...s и умножим тези неравенства почленно, получаваме след съкращения f(s+1)≤2^s-1f(2), т.е. m(s+1)≤2^s-1.3-1.

Доказахме Следствие 5. m(s)≤ 3.2^s-2-1 при s≥2.

Ще докажем :

Да означим съседите на v₀ с v₁, v₂, ...,v_d, d=d(v₀) и да разгледаме графа Г=G-{ v₀, v₁, v₂, ...,v_d }. Броят на върховете на Г е m(s)-d-1≤m(s)-s-1 и Г също не съдържа триъгълници. Ще докажем, че χ(Г)≥s-1. Наистина да допуснем, че χ(Г)≤s-2 и да вземем едно върхово (s-2)-оцветяване на Г. Да оцветим върховете v₁, v₂, ...,v_d (никои два от тях не са съседни, защото иначе в G ще има триъгълник с връх v₀) в някой цвят, различен от цветовете използвани в Г. Върха v₀ ще оцветим в някой от цветовете, използвани в Г. Получаваме върхово (s-1)-оцветяване на G, което е невъзможно.

И така, намерихме граф Г с не повече от m(s)-s-1 върха , който не съдържа триъгълници и χ(Г)≥s-1.

От това, че χ(Г)≥s-1 лесно следва, че в Г има подграф Г’, за който χ(Г’)=s-1 . Ако χ(Г)=s-1, разбира се, можем да вземем Г’=Г. Ако χ(Г)>s-1 и значи χ(Г)=s, ще се възползваме от очевидния факт, че отстранявайки връх на един граф (заедно със всички ребра през него)можем да намалим хроматичното му число най-много с единица. Така че, ако отстраняваме от Г последователно върхове дотогава, докато хроматичното число на оставащия подграф стане равно на s-1, ще достигнем до желания подграф Г’.

По такъв начин намерихме граф Г’ без триъгълници с не повече от m(s)-s-1 върха и χ(Г’)=s-1. Това показва, че m(s-1)≤m(s)-s-1, т.е. установеното неравенство (14).

Теорема 5 е доказана.

Неравенство (14) ще запишем във вида m(k)- m(k-1)≥1+k при k≥4.

След това, ще дадем на k стойности k=r, r+1,…,s (r≥4) и ще съберем почленно получените неравенства. Получаваме

Следствие 6. Ако s≥r≥4, тогава (15) m(s)≥m(r-1)+(s-r+1).

Тъй като m(3)=5, от (15) при r=4 получаваме (16) m(s)≥, при s≥3.

От (16) при s=4 следва, че m(4)≥10. По-горе намерихме граф (означихме го с G₄) с единадесет върха, без триъгълници и с χ(G₄)=4. Следователно m(4)≤11.

3.4. Единственост на минималния граф без триъгълници и хроматично число четири

Теорема 6. G₄ е единственият граф с не повече от единадесет върха, който не съдържа триъгълници и има хроматично число четири.

Док: Нека G е граф без триъгълници, χ(G)=4 и броят на върховете на G не надминава единадесет. Да означим с w един връх с максимална степен на графа G и нека A е множеството от всички съседи на w. Очевидно d(w)≥3, тъй като в противен случай съгласно (12) 4-χ(G)≤1+d(G)≤3. Ако допуснем, че d(w)=3, от теорема 2 ще следва, че G съдържа 4-клика, което не е вярно.

Следователно |A|=d(w)≥4.

Множеството A е независимо (иначе в G ще има триъгълник).

Да означим с B множеството на всички върхове на G, които са различни от w и не са съседни на него.

Графътне е върхово 2-оцветим. Наистина, ако допуснем, че е върхово 2-оцветим, ще оцветим върховете от A в трети цвят, а върха w в някой от първите два и по такъв начин ще получим върхово 3-оцветяване на G, което е невъзможно.

Тъй като не е върхово 2-оцветим, от теоремата на Кьониг следва, че има подграф от вида C_2r+1. Тъй катоне съдържа триъгълници то r≥2. От друга страна, B съдържа най-много 11-|A|-1 на брой върхове и тъй като |A|≥4, графът има не повече от шест върха.

Следователно има подграф C₅. върховете на C₅ по реда на обхождането ще означим с v₁, v₂, v₃, v₄, v₅.

Тъй като извън A има поне шест върха, то в A има най-много пет върха.

Отначало ще установим, че за всеки два несъседни върха от C₅ има връх от A, който е съседен и на двата.

Да забележим, че всеки връх u на А може да се оцвети в c₁ или c₂ така, че да се получи върхово 3-оцветяване на G. Наистина, ако uА, u не е съседен на поне един от върховете v₁ и v₃ – например v₁. Ако u е съседен на v₃, не можем да го оцветим в c₂, но можем да го оцветим в c₁, тъй като не е съседен на v₄ (иначе [u, v₃, v₄] е триъгълник) и значи не е съседен на никой връх, предварително оцветен в c₁. По същите съображения може да оцветим u в c₁, ако е съседен на v₅. Но ако u не е съседен нито на v₃, нито на v₅, тогава можем да го оцветим в c₂ (тъй като не е съседен на върхове, предварително оцветени в c₂).

Окончателно получаваме върхово 3-оцветяване на G, а това е невъзможно.

По такъв начин доказахме, че за всеки два несъседни върха на C₅ има връх от А, който е съседен и на двата.

Ще означим с u₁ връх от А, който е съседен едновременно на v₅ и v₂, с u₂ – връх от А, съседен едновременно на v₁ и v₃ и т.н. Ясно е, че u_i≠u_j при i≠j , тъй като никой връх от А не може да бъде съседен на повече от два върха от C₅ (иначе в ще има триъгълник).

Доказахме, че G₄ е подграф на G. Присъединяването на ново ребро към G₄ очевидно води до образуване на триъгълник. Следователно G=G₄.

Всеки връх от А е съседен на най-много два върха от C₅. Тъй като има пет двойки несъседни върхове от C₅, то със сигурност има такава двойка несъседни върхове – например v₁ и v₃ – от C₅, че никой връх от А не е съседен едновременно на v₁ и v₃. Ще направим върхово 3-оцветяване както в 1 на всички върхове от А, от C₅ и на w.

Ако в G няма други върхове, тогава получаваме противоречието, че G е върхово 3- оцветим.

2.1 Впрочем до същото противоречие достигаме и когато в G има връх a, a≠w, aА, aC₅, но този връх не е съседен на v₂. За да се убедим в това, достатъчно е допълнително да оцветим a в c₃.

И така, остана за разглеждане случая, когато в G има връх a, a≠w, aА, aC₅, който е съседен на v₂.

Ако никой връх от А не е съседен едновременно на v₂ и v₄, тъй като а не е съседен на v₃ както по-горе (в 2.1), ще получим върхово 3-оцветяване на G (сега ролята на v₁ и v₃ се играе от v₂ и v₄, а ролята на v₂ – от v₃).

Поради това можем да считаме, че има връх u₁ от А, който е съседен едновременно на v₂ и v₄. тъй като d(G)=|A| =4, то v₂ не е съседен на никой друг връх на G освен на a, v₁, v₃, u₁. В такъв случай останалите върхове на A – u₂, u₃ и u₄ – не са съседни на v₂. Върхът u₁ не е съседен на v₅, защото иначе в G ще има триъгълник.

И така, никой връх от А не е съседен едновременно на двата несъседни върха v₂ и v₅ от

C₅, а върхът a не е съседен на v₁ (на фиг. 3 е начертана част от графа ).

Както във 2.1 следва, че G е върхово 3-оцветим. Отново достигнахме до противоречие.

Теорема 6 е доказана.

От теорема 6 тривиално получаваме

Следствие 7. m(4)=11.

От следствие 6 и следствие 7 непосредствено се получава

Неравенство (17) е по-силно от неравенство (16), което

изведохме в предния пункт.