رنگ‌آمیزی ‎‎ نو با ‎$k$‎ رنگ، رنگ‌آمیزیی است که هر یال را به یکی از اعداد ‎$1$‎ تا ‎$k$‎ نسبت می‌دهد. در یک رنگ‌آمیزی نو، حذف تمامی یالهای هر رنگ ‎$i$‎ ($i \in \{1‎, ‎2‎, ‎\ldots k\}$) گراف باقیمانده را همبند نگه می‌دارد. توجه کنید که این رنگ‌آمیزی تنها برای گراف‌هایی قابل انجام است که همبنداند و یال برشی ندارند. کم‌ترین تعداد رنگ لازم برای رنگ‌آمیزی نوِ هر گراف ‎$n$‎ رأسی بدون یال برشی چقدر است؟ برای گفتهٔ خود دلیل بیاورید.

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