•رنگ آمیزی رأس ها : در این حالت رنگ‌آمیزی‌ باید به گونه ای باشد که درآن هیچ دو راس مجاوری هم رنگ نباشند.

•

•رنگ آمیزی یال ها : در این حالت رنگ‌آمیزی‌ باید به گونه ای باشد که درآن هیچ دو یال مجاوری هم رنگ نباشند.

•

•رنگ آمیزی سطح : در این حالت رنگ آمیزی باید به گونه ای باشد که در آن هیچ دو ناحیه ی گراف که مرز مشترک دارند همرنگ نباشند.

• اولین نتیجه‌های بدست آمده در مورد رنگ آمیزی گراف از تلاش‌های انجام شده بر روی گراف‌های مسطح برای حل مساله رنگ آمیزی نقشه بدست آمد.

• در آن زمان Francis Guthrie ادعا کرد که رنگ آمیزی نقشه ایالت‌های مختلف بریتانیا روی نقشه، به طوری که هیچ دو ایالت مجاوری همرنگ نشوند، می‌تواند با ۴ رنگ انجام شود. برادر Guthrie این مساله را برای معلم ریاضی خود Augustus de Morgan، در College of Londonفرستاد و او این مساله را در سال ۱۸۲۵ میلادی در نامه‌ای که به William Hamilton نوشت مطرح کرد.

• در سال ۱۸۷۹ Arthur Cayley این مساله را در انجمن ریاضی شهر لندن مطرح کرد. در همان سال Alfred Kempe، نتایج بدست آمده را منتشر کرد و برای یک دهه تصور می‌شد این مساله حل ‌شده ‌است. برای تلاش‌های Kempe در این زمینه او به عنوان یکی از اعضای جامعه سلطنتی و بعدها به عنوان ریاست انجمن ریاضی شهر لندن انتخاب شد.

• در سال 1820، Heawood ادعا کرد که استدلال Kempe اشتباه بوده‌است و اثبات این مساله را برای ۵ رنگ منتشر کرد.

 

• در قرن بیستم تلاش‌های زیادی برای اثبات روش‌های رنگامیزی نقشه با ۴ رنگ صورت گرفت که در نهایت در سال ۱۹۷۶ این مسأله به وسیله Kenneth Appel و Wolfgang Haken اثبات شد ولی به دلیل استفاده از کامپیوتر برای اثبات مساله، به آن اعتنایی نشد.

 

رنگ آمیزی رأس ها :