روابطي بين عدد تشخيص و پارامترهاي ديگر گراف ‌ها

يك رنگ‌آميزي تشخيص از گرافي ساده مانند G، عبارت است از يك رنگ‌آميزي رئوس G به‌طوري‌كه تنها خودريختي‌اي از G كه اين رنگ‌آميزي را حفظ مي‌كند، خودريختي هماني باشد. به‌عبارت‌ديگر، اين رنگ‌آميزي همه‌ي تقارن‌هاي G را «مي‌شكند». عدد تشخيص يك گراف مانند G، كه با D(G)نمايش داده مي‌شود، كوچك‌ترين تعداد رنگ مورد نياز براي يك رنگ‌آميزي تشخيص~G است. در اين مقاله، علاوه بر مطالعه‌ي برخي از روابط موجود بين D(G) و پارامترهاي مهم گرافي، مفهوم (D,\alpha)-عادي بودن يك گراف را تعريف مي‌كنيم كه بيانگر مقايسه‌ي بين D(G) و عدد استقلال \alpha(G) است. سپس طيف وسيعي از گراف‌ها را از ديدگاه (D,\alpha)-عادي بودن مطالعه و رده‌بندي‌هايي را براي گراف‌هاي دوبخشي، چندبخشي كامل، گراف‌هاي جانسون تعميم‌يافته و حاصل‌ ضرب‌هاي دكارتي و گراف‌هاي خط برخي از گراف‌ها ارائه مي‌كنيم.