גרף 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> תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם.

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