ในทฤษฎีกราฟการระบายสีหรือการติดป้ายที่แตกต่างกันของกราฟ คือการกำหนดสีหรือป้ายให้กับจุดยอดของกราฟ ซึ่งจะทำลาย สมมาตรที่ไม่ใช่ สมมาตรพื้นฐานทั้งหมดของกราฟการระบายสีไม่จำเป็นต้องเป็นการระบายสีที่ถูกต้อง : จุดยอดที่อยู่ติดกันสามารถมีสีเดียวกันได้ สำหรับกราฟที่ระบายสีแล้ว จะต้องไม่มีการจับคู่แบบหนึ่งต่อหนึ่งระหว่างจุดยอดกับตัวมันเองที่รักษาทั้งความติดกันและการระบายสีไว้ จำนวนสีขั้นต่ำในการระบายสีที่แตกต่างกันเรียกว่าจำนวนที่แตกต่างกันของกราฟ

การระบายสีที่แตกต่างกันและหมายเลขที่แตกต่างกันได้รับการแนะนำโดยAlbertson & Collins (1996)ซึ่งได้ยกตัวอย่างประกอบดังต่อไปนี้ โดยอิงจากปริศนาที่ Frank Rubin เคยตั้งไว้ก่อนหน้านี้: "สมมติว่าคุณมีพวงกุญแจสำหรับประตูหลายบาน แต่ละดอกเปิดได้เพียงประตูเดียว แต่คุณมองไม่เห็นความแตกต่างระหว่างกุญแจทั้งหมด คุณต้องใช้สีจำนวนกี่สีจึงจะสามารถระบายสีด้ามกุญแจในลักษณะที่ทำให้คุณสามารถระบุแต่ละดอกได้อย่างเฉพาะเจาะจง?" ^{[ 1 ]}ตัวอย่างนี้ได้รับการแก้ไขโดยใช้การระบายสีที่แตกต่างกันสำหรับกราฟวงจรด้วยการระบายสีดังกล่าว แต่ละดอกจะถูกระบุได้อย่างเฉพาะเจาะจงด้วยสีของมันและลำดับของสีที่อยู่รอบๆ^{[ 2 ]}

กราฟจะมีหมายเลขที่โดดเด่นเป็นหนึ่งก็ต่อเมื่อเป็นกราฟอสมมาตร^{[ 3 ]}ตัวอย่างเช่นกราฟ Fruchtมีการระบายสีที่โดดเด่นด้วยสีเดียวเท่านั้น

ในกราฟสมบูรณ์การระบายสีที่แตกต่างกันเพียงอย่างเดียวคือการกำหนดสีที่แตกต่างกันให้กับแต่ละจุดยอด เพราะหากจุดยอดสองจุดถูกกำหนดสีเดียวกัน จะมีสมมาตรที่สลับจุดยอดทั้งสองนั้น ทำให้จุดยอดที่เหลือยังคงอยู่ที่เดิม ดังนั้น จำนวนที่แตกต่างกันของกราฟสมบูรณ์K คือnอย่างไรก็ตาม กราฟที่ได้จากK โดยการเชื่อมต่อจุดยอดที่มีดีกรีหนึ่งเข้ากับแต่ละจุดยอดของK จะมีจำนวนที่แตกต่างกันน้อยกว่าอย่างมาก แม้ว่าจะมีกลุ่มสมมาตรเดียวกันก็ตาม กล่าวคือ มีการระบายสีที่แตกต่างกันด้วยสี ซึ่งได้มาจากการใช้ คู่ สีที่เรียงลำดับ ต่างกันสำหรับแต่ละคู่ของจุดยอด K และจุดยอดข้างเคียงที่เชื่อมต่อ^{[ 2 ]}${\displaystyle \lceil {\sqrt {n}}\rceil }$

สำหรับกราฟวงจรที่มีจุดยอดสาม สี่ หรือห้าจุด จำเป็นต้องใช้สามสีในการสร้างการระบายสีที่แตกต่างกัน ตัวอย่างเช่น การระบายสีสองสีของวงจรห้าจุดทุกวงจรจะมีสมมาตรการสะท้อนในแต่ละวงจรเหล่านี้ การกำหนดสีที่ไม่ซ้ำกันให้กับจุดยอดที่อยู่ติดกันสองจุด และใช้สีที่สามสำหรับจุดยอดที่เหลือทั้งหมด จะส่งผลให้ได้การระบายสีที่แตกต่างกันสามสี อย่างไรก็ตาม วงจรที่มีจุดยอดหกจุดขึ้นไปมีการระบายสีที่แตกต่างกันโดยใช้เพียงสองสี กล่าวคือ ปริศนาพวงกุญแจของแฟรงก์ รูบิน ต้องใช้สามสีสำหรับวงแหวนที่มีกุญแจสาม สี่ หรือห้าดอก แต่ใช้เพียงสองสีสำหรับกุญแจหกดอกขึ้นไปหรือสำหรับกุญแจสองดอก^{[ 2 ]}ตัวอย่างเช่น ในวงแหวนที่มีกุญแจหกดอกที่แสดงไว้ กุญแจแต่ละดอกสามารถแยกแยะได้ด้วยสีและด้วยความยาวของบล็อกที่อยู่ติดกันของกุญแจที่มีสีตรงข้ามกัน: มีเพียงกุญแจดอกเดียวสำหรับแต่ละการรวมกันของสีกุญแจและความยาวของบล็อกที่อยู่ติดกัน

กราฟไฮเปอร์คิวบ์แสดงปรากฏการณ์ที่คล้ายกับกราฟวงจร กราฟไฮเปอร์คิวบ์สองมิติและสามมิติ (วงจร 4 และกราฟของลูกบาศก์ ตามลำดับ) มีเลขเด่นคือสาม อย่างไรก็ตาม กราฟไฮเปอร์คิวบ์ทุกกราฟที่มีมิติสูงกว่าจะมีเลขเด่นเพียงสอง^{[ 4 ]}

กราฟPetersenมีเลขเด่น 3 อย่างไรก็ตาม นอกจากกราฟนี้และกราฟสมบูรณ์แล้วกราฟ Kneser ทั้งหมด มีเลขเด่น 2 ^{[ 5 ]}ในทำนองเดียวกัน ในบรรดากราฟ Petersen ทั่วไปมีเพียงกราฟ Petersen เองและกราฟของลูกบาศก์เท่านั้นที่มีเลขเด่น 3 ส่วนที่เหลือมีเลขเด่น 2 ^{[ 6 ]}

จำนวนที่แตกต่างกันของต้นไม้กราฟระนาบและกราฟช่วงสามารถคำนวณได้ในเวลาพหุนาม^{[ 7 ] [ 8 ] [ 9 ]}

ความซับซ้อนที่แท้จริงของการคำนวณจำนวนที่แยกแยะนั้นไม่ชัดเจน เนื่องจากมีความเกี่ยวข้องอย่างใกล้ชิดกับความซับซ้อนของกราฟไอโซมอร์ฟิซึม ซึ่งยังไม่ทราบแน่ชัด อย่างไรก็ตาม ได้มีการแสดงให้เห็นแล้วว่าอยู่ในกลุ่มความซับซ้อนAM ^{[ 10 ]}นอกจากนี้ การทดสอบว่าจำนวนสีที่แยกแยะมีค่าไม่เกินสามนั้นเป็นปัญหาNP -hard [ ^{9 ] และ}การทดสอบว่ามีค่าไม่เกินสองนั้น "ยากอย่างน้อยเท่ากับกราฟออโตมอร์ฟิซึม แต่ไม่ยากกว่ากราฟไอโซมอร์ฟิซึม" ^{[ 11 ]}

การระบายสีกราฟที่กำหนดจะมีความโดดเด่นสำหรับกราฟนั้นก็ต่อเมื่อมีความโดดเด่นสำหรับกราฟส่วนเติมเต็มเท่านั้น ดังนั้นกราฟทุกกราฟจึงมีหมายเลขที่โดดเด่นเหมือนกับกราฟส่วนเติมเต็ม^{[ 2 ]}

สำหรับกราฟG ทุก กราฟ จำนวนการแยกแยะของGจะเป็นสัดส่วนสูงสุดกับลอการิทึมของจำนวนออโตมอร์ฟิซึมของGหากออโตมอร์ฟิซึมก่อตัวเป็นกลุ่มอาเบเลียน ที่ไม่ใช่กลุ่มย่อย จำนวนการแยกแยะจะเป็นสอง และหากก่อตัวเป็นกลุ่มไดเฮดรัลจำนวนการแยกแยะจะเป็นสามอย่างมาก^{[ 2 ]}

สำหรับกลุ่มจำกัด ทุกกลุ่ม จะมีกราฟที่มีกลุ่มนั้นเป็นกลุ่มออโตมอร์ฟิซึม โดยมีเลขแยกแยะสอง^{[ 2 ]}ผลลัพธ์นี้ขยายทฤษฎีบทของฟรุคท์ที่ว่ากลุ่มจำกัดทุกกลุ่มสามารถรับรู้ได้ว่าเป็นกลุ่มสมมาตรของกราฟ

การระบายสีแบบแยกแยะที่เหมาะสมคือการระบายสีแบบแยกแยะซึ่งเป็นการระบายสีที่เหมาะสมเช่นกัน กล่าวคือ จุดยอดที่อยู่ติดกันสองจุดจะมีสีที่แตกต่างกัน จำนวนสีขั้นต่ำในการระบายสีแบบแยกแยะที่เหมาะสมของกราฟเรียกว่าจำนวนสีโครมาติกแบบแยกแยะของกราฟ^{[ 12 ]}