การระบายสีแบบเท่าเทียมในกราฟ
Equitable Colorings in Graphs
Keywords:
การระบายสีแบบเท่าเทียม , รงคเลขแบบเท่าเทียมAbstract
กราฟ G สามารถระบายสีด้วยสี k สีแบบเท่าเทียม ถ้าสามารถแบ่งกั้นเซตของจุดยอดเป็นเซตอิสระจำนวน k เซต โดยที่จำนวนจุดยอดของเซตสองเซตใดๆ แตกต่างกันอย่างมากที่สุดเท่ากับหนึ่งจุด รงคเลขแบบเท่าเทียมของกราฟ G เขียนแทนด้วย X= (G) คือ จำนวนเต็มบวก k ที่น้อยที่สุดซึ่ง G สามารถระบายสีด้วยสี k สีแบบเท่าเทียมได้ ในบทความนี้ เรารวบรวมและให้ความเห็นเกี่ยวกับผลการศึกษาที่เกี่ยวข้องกับการระบายสีแบบเท่าเทียม ข้อความคาดการณ์เกี่ยวกับการระบายสีแบบเท่าเทียม รงคเลขแบบเท่าเทียมในกราฟบางประเภท รวมถึงเสนอปัญหาเปิดสำหรับการระบายสีแบบเท่าเทียมด้วย A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The equitable chromatic number of G, denoted by X= (G), is the smallest positive integer k such that G is equitably k-colorable. In this article, we collect and give comments about the results concerning the equitable coloring about the equitable coloring conjectures and the equitable chromatic numbers in some classes of graphs. Moreover, we give some open problems in this topic.References
Bollobas, B. & Guy, R. K. (1983). Equitable and proportional coloring of trees, Journal of Combinatorial Theory, Series B, 34, 177–186.
Brooks, R. L. (1941). On colouring the nodes of a network, Proceedings of the Cambridge Philosophical Society, 37, 194–197.
Chen, B.-L. & Lih, K.-W. (1994). Equitable coloring of trees, Journal of Combinatorial Theory, Series B, 61, 83–87.
Chen, B.-L., Lih, K.-W.,& Wu, P.-L. (1994). Equitable colouring and the maximum degree, European Journal of Combinatorics, 15, 443–447.
Chen, B.-L., Lih K.-W., & Yan, J.-H. (1998). Equitable coloring of interval graphs and products of graphs, manuscript.
Fidytek, R., Furmanczyk, H., & Zylinski, P. (2009). Equitable coloring of Kneser graphs, Discussiones Mathematicae Graph Theory, 29(1), 119–142.
Furmanczyk, H. (2006). Equitable coloring of graph products, Opuscula mathematica, Vol 26, No. 1, 31–44.
Guy, R. K. (1975). Monthly research problems, 1969-1975, American Mathematical Monthly, 82, 995–1004.
Hajnal, A. & Szemeredi, E. (1970). Proof of conjecture of Erdos, in: Renyi A. and Sos, V. T. editors., Combinatorial Theory and Its Applications, Vol. II, Colloquium of Mathematics Society Janos Bolyai 4 (North- Holland, Amsterdam), 601–623.
Jensen, T. R. & Toft, B. (1995). Graph Coloring Problems, John Wiley & Sons, New York.
