גרף n-צביע – הבדלי גרסאות

אם מסמנים ב <math>\triangle(G)</math> את הדרגה המקסימלית של צומת ב-<math>\ G</math> אז <math>\chi(G)\leq \triangle(G)+1</math>. תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור <math>k\in \mathbb{N}</math> בכל תת-גרף מושרה <math>\ H</math> של <math>\ G</math> קיים צומת <math>v\in H</math> כך ש-<math>d_H (v)\leq k</math> אז <math>\chi(G)\leq k+1</math>. עבור <math>k=\triangle(G)</math> תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור [[גרף שלם]] על n צמתים <math>\triangle(G)=n-1</math> ו <math>\ \chi(G) = n</math> ועבור מעגל אי-זוגי <math>\triangle(G)=2</math> ו <math>\ \chi(G) = 3</math> ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם '''משפט ברוקס''' קובע כי לכל שאר הגרפים <math>\chi(G)\leq \triangle(G)</math>.

 

 

נסמן ב-<math>\ \alpha(G)</math> את גודל תת-הקבוצה ה[[קבוצה בלתי תלויה (תורת הגרפים)|בלתי תלויה]] הגדולה ביותר, אז <math>\ \chi(G)\geq \frac{n}{\alpha(G)}</math>.