تلوين الخارطة أحد اكثر المسائل شهرة وبحثا في نظرية المخططات , ولها الكثير من التطبيقات العملية وكثير من الحدسيات تتعلق بهذه المسألة وما زال كثير من علماء علوم الحاسوب والرياضيات يحاولون فك هذه الحدسيات .
وهذه المسألة هي تخصيص "لون" لاحد عناصر المخطط بحيث تتحقق مجموعة شروط محددة , لعل ابسط الصيغ هذه المسألة هي تلوين رؤوس المخطط بحيث لا يوجد رأسان متجاوران لهما نفس اللون . وهذا النوع من التلوين يسمى "تلوين الرؤوس" , وبشكل مشابه نعرف "تلوين الاضلاع" وهو تلوين الاضلاع بحيث لا يوجد ضلعان يشتركان في رأس لهما نفس اللون , و"تلوين الوجوه" في مخطط مستو هو تخصيص لون لكل وجه او منطقة بحيث لا يوجد منطقتين تشتركان بنفس الحدود لهما نفس اللون .