09 April 2020



Seminar Internasional BaSIC 2012 Hal C71 – C75 ISBN 978-979-25-6033-6

September 28, 2012 by   Leave a comment

Applying a Proper m-Colorings of The Vertices of a Graph for Class Scheduling Problem

Ani Dijah Rahajoe1), Edi Winarko2)
1)Informatics Engineering, Bhayangkara University, Surabaya (anidrahayu@gmail.com)
2)Fac. Of Mathematics and Natural Sciences, Universitas Gadjah Mada, Yogyakarta (ewinarko@ugm.ac.id)

The graph coloring algorithm for finding the proper m-colorings of the vertices of a graph has been proved that every graph with n vertices and maximum vertex degree Δ must have chromatic number χ(G) less than or equal to Δ+1 and that this algorithm will always find a proper m-colorings of the vertices of G with m less than or equal to Δ +1. It has also been proved that this condition is the best possible in terms of n and Δ by explicitly constructing graphs for which the chromatic number is exactly Δ+1.
In this paper, the algorithm is applied to real data to examine if the optimal results can be obtained. This paper explores the application of the vertex coloring algorithm for finding a proper m-colorings on the class scheduling problem. The problem is to create schedule of courses which consists of 18 courses and involves about 500 students. The result of experiments shows that the algorithm finds a proper m-colorings of the courses for m equal to the chromatic number χ(G). Collision course do not occur and the resulting schedule is optimal without the exchange of schedule.
Keywords:the proper m-colorings, vertex degree, chromatic number, class scheduling problem.

Disajikan pada Seminar Internasional Basic Science International Conference 2012 dan dipublikasikan pada Prosiding 2nd BASIC SCIENCE Intenational Conference 2012
No ISBN 978-979-25-6033-6.
PDF File

Leave a Reply