การระบายสีแบบเท่าเทียมในกราฟ

Abstract

บทคัดย่อ

กราฟ G สามารถระบายสีด้วยสี k สีแบบเท่าเทียม ถ้าสามารถแบ่งกั้นเซตของจุดยอดเป็นเซตอิสระจำนวน k เซต โดยที่จำนวนจุดยอดของเซตสองเซตใดๆ แตกต่างกันอย่างมากที่สุดเท่ากับหนึ่งจุด รงคเลขแบบเท่าเทียมของกราฟ G เขียนแทนด้วย χ=(G) คือจำนวนเต็มบวก k ที่น้อยที่สุดซึ่ง G สามารถระบายสีด้วยสี k สีแบบเท่าเทียมได้ ในบทความนี้ เรารวบรวมและให้ความเห็นเกี่ยวกับผลการศึกษาที่เกี่ยวข้องกับการระบายสีแบบเท่าเทียม ข้อความคาดการณ์เกี่ยวกับการระบายสีแบบเท่าเทียม รงคเลขแบบเท่าเทียมในกราฟบางประเภท รวมถึงเสนอปัญหาเปิดสำหรับการระบายสีแบบเท่าเทียมด้วย

คำสำคัญ : การระบายสีแบบเท่าเทียม รงคเลขแบบเท่าเทียม

Abstract

A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets in such a waythat the numbers of vertices in any two sets differ by at most one. The equitable chromatic number of G, denotedby χ=(G), is the smallest positive integer k such that G is equitably k-colorable. In this article, we collect and givecomments about the results concerning the equitable coloring about the equitable coloring conjectures and theequitable chromatic numbers in some classes of graphs. Moreover, we give some open problems in this topic.

Keywords : equitable coloring, equitable chromatic number