اگر $c$‌یک رنگ‌آمیزی راسی معتبر گراف $G$‌با عددهای طبیعی باشد، $\sum_{u\in V(G)} c(u)$ را مجموع رنگی $c$ می‌نامیم. رنگ‌آمیزی $c_0$ که در بین تمام رنگ‌آمیزی‌های راسی معتبر $G$ با عددهای طبیعی کم‌ترین مجموع رنگی را دارد، ‌یک رنگ‌آمیزی بهینه برای $G$ نامیده می‌شود. مجموع رنگی یک رنگ‌آمیزی بهینه را مجموع رنگی $G$‌ می‌نامیم و به $\sum (G)$ نمایش می‌دهیم. همچنین کم‌ترین تعداد رنگ‌های لازم برای یک رنگ‌آمیزی بهینه $G$‌را به $s(G)$ نمایش می‌دهیم.

الف) نشان دهید اگر $c_0$ یک رنگ‌آمیزی بهینه برای $G$‌باشد، آن‌گاه برای هر راس $u$ در $G$ داریم $c_0(u)\leq 1+deg\quad u$.

ب) گرافی چون $G$ با $s(G)> x(G)$ مثال بزنید.

پ)برای هر گراف $G$‌ نشان دهید:

$$\sum (G) \leq \frac{1+s(G)}{2} n(G)$$

• سوال بعد
• سوال قبل