1. Pangasinan State University-Asingan Campus, Pangasinan, Philippines.

*             Correspondence: jrmiguel_ms@psu.edu.ph

Keywords: graph coloring, course timetable scheduling, hard constraints, soft constraints

1. INTRODUCTION

An author [1] contended that “regardless of the teaching model and methods used, effective instruction begins with careful, thorough, and organized planning on the part of the teacher”.  Planning has been an important aspect of the education process for many years.  Early planning models developed by experts such as Tyler followed a rational model: develop objectives, develop activities to help students achieve objectives, and evaluate the students to determine if the objectives have been met [2].  However, the planning process has evolved to focus more on designing learning activities that meet the diverse needs of the students to ensure that learning has taken place [3,4]. Planning practices are necessary prerequisites to effective teaching [5,6].  Their importance is illustrated in the guidelines produced by national organizations such as The Interstate New Teacher Assessment and Support Consortium (INTASC), The National Board for Professional Teaching Standards (NBPTS), and The National Council of Teachers of Mathematics (NCTM).  Planning time is deemed important by teachers at the grassroots level in order for them to develop thought-provoking lessons that allow students to make connections and form meaning as well as to reflect on previous lessons in order to make improvements for subsequent lessons [7,8].   Specifically, collaborative planning is recommended as a method to improve instruction. An author [9] believed there was no infrastructure to encourage communication among teachers to improve their teaching or solve work place problems. An author [9] contended that impediments to ideal mathematics instruction consisted of lack of preparation time and lack of collaboration with peers.  An author [10] found that teachers who collaborated with other teachers used higher levels of reformed mathematics instruction, and it was a strong recommendation of the NCTM that math teachers reform mathematics instruction. An author [11] described a successful program in which library media specialists (LMS) collaborated with content area teachers in order to better prepare lessons for the students.  An author [12] studied two teams of teachers at the elementary school level.  He determined that the team who had a longer planning time utilized a greater variety of team-teaching strategies than the other team.  A study [13] directly studied the impact of collaborative planning on the quality of lesson plans, and findings showed evidence that a significant positive correlation existed between collaboration and lesson plans that received higher scores on a lesson plan scoring system.  Collaborative planning is currently an emphasis in several educational areas such as classes where inclusion occurs, the middle school approach to teaching, and block scheduling which usually occurs at the high school level [14,15]. The NCTM is one of the national organizations that suggests planning time is critical to effective teaching and implementation of the standards.  In 2000, Lee V. Stiff, NCTM president, urged a renewed attention to good lesson planning and lesson implementation in order to improve mathematics learning [16].  The main recommendation of the NCTM is the development of conceptual understanding of mathematics through an inquiry approach to teaching and learning that influences students’ meaningful learning of mathematics [17]. The NCTM’s most recent standards document, Principles and Standards, outlines its recommendations on the mathematical content that should be taught and the most effective methods to instill the content in the students.  Specifically, the NCTM emphasizes five process standards that will help define effective teaching: problem solving, reasoning and proof, communication, connections, and representations [18].  The process standards may be implemented by various instructional strategies such as cooperative learning, writing, and mathematical discourse [19].  Other instructional techniques that helped improve the NCTM process standards include manipulatives and technology [20,21].  The literature is abundant on effective instruction of mathematics. Graph theory originated in 1736 with Euler’s solution to the Königsberg bridge problem, which introduced the concept of a Eulerian graph [22]. In the same era, Gustav Kirchhoff developed the idea of a tree, a connected graph without cycles, which he applied to calculate electrical currents in networks and later to enumerate chemical molecules. An author [18] introduced the concepts of complete graphs and bipartite graphs. The famous four-color problem was discovered by [21], and while initial studies focused on planar graphs and map coloring [5], the problem was only solved by [14]. In 1890, Heawood proved the five-color theorem, stating that every planar map can be colored with no more than five colors [16]. George David Birkhoff further advanced the field in 1912 by introducing the chromatic polynomial to study coloring problems in algebraic graph theory [8]. Graph coloring has numerous real-world applications, including map coloring, scheduling, parallel computation, network design, sudoku, register allocation, and bipartite graph detection. It plays a crucial role in solving complex optimization problems, such as conflict resolution and the optimal partitioning of mutually exclusive events, which includes course timetable scheduling [12]. An author [8] proposed a university timetabling system based on graph coloring and constraint manipulation. They described heuristic algorithms for graph coloring and room allocation, demonstrating how these could be combined for effective timetabling, particularly for examinations. An author [4] introduced graph coloring methods to optimize timetable scheduling problems. A study [7] was among the early researchers to apply and modify these methods for university timetabling. Timetabling involves allocating resources to objects in the space-time domain, subject to constraints, to meet a set of desirable objectives. University course timetabling requires scheduling meetings between instructors and students while satisfying various essential conditions. The problem involves allocating courses to limited resources such as time slots, lecturers, lecture rooms, labs, and student groups, ensuring all hard constraints are met and as many soft constraints as possible are satisfied. For instance, courses taught by the same instructor or requiring the same classroom must be scheduled at different times, and students may need to take multiple courses concurrently without conflicts. This allocation problem is a typical graph coloring challenge. This study addressed the course timetable scheduling problem using graph coloring to prevent conflicts.

2. MATERIALS AND METHODS

The study developed a mathematical model for scheduling major math courses for the Bachelor of Secondary Education Major in Mathematics students at Pangasinan State University-Asingan Campus. The model incorporates both hard and soft constraints, considering subjects for each year level, the number of instructors, and available lecture rooms. The optimal solution is found by determining the minimal colorings for the corresponding graph. An effective timetable is crucial for the institution’s performance, enabling it to meet evolving subject demands and combinations cost-effectively while satisfying various constraints. For solving Course Timetable scheduling problems using graph coloring, the problem is first formulated in the form of a graph were courses act as vertices. Depending on type of graph created, edges are drawn accordingly. In a conflicting graph, edges are drawn between conflicting courses having common students. Courses can conflict due to common teachers, common classrooms in addition to common students. In such cases, the conflict graph must consider course, teacher and room conflicts simultaneously. As mentioned earlier, there can be various aspects of a scheduling problem. When teachers are involved in resources, other factors like availability of teachers, subject area preferred by each teacher acts as additional data inputs which needs to be provided for making a complete schedule [23]. In the Bachelor of Secondary Education major in mathematics there are ten (10) major courses/subjects to be offered for the first semester for the first year, second year, and third year level students. There were three (3) faculty members handling these courses, 3 rooms available, and the given time periods for its offerings should be 1 hour every MWF (Monday, Wednesday, Friday) and 1 and a half hours every TTh (Tuesday, Thursday). Each subject should have 3 hours allotted per week. The study found a minimum number of time slots/periods to schedule all the courses without conflict on the teacher and students’ assignments. Hard constraints: Two or more subjects taught by the same teacher cannot be scheduled for the same time slot/period. Subjects which enroll the same set of students cannot be scheduled for the same time slot/period. Each subject must be scheduled for exactly one time slot/period and one room. Soft constraints: Math instructors prefer the time period of weekday mornings for major courses. Students on the same year level should stay on the same room all throughout their weekly schedule.

3. RESULTS AND DISCUSSION

Table 01: BSE Math Major Course Offerings for the 1st Semester

First Year BSE-Math	Second Year BSE-Math	Third Year BSE-Math
Math 101: History of Mathematics	Math 107: Calculus I with Analytic Geometry	Math 109: Calculus III
Math 102: College and Advanced Algebra	Math 105: Logic and Set Theory	Math 114: Linear Algebra
	Math 106: Elementary Statistics and Probability	Math 115: Advanced Statistics
	Math 111: Modern Geometry	Math 119: Research in Mathematics

Let the following variables denote each of the subjects offered:

S₁ = Math 101

S₂ = Math 102

S₃ = Math 107

S₄ = Math 105

S₅ = Math 106

S₆ = Math 111

S₇ = Math 109

S₈ = Math 114

S₉ = Math 115 S₁₀ = Math 119

The following variables denote each of the faculty members in the department teaching major math subjects.

T₁ = Instructor 1

T₂ = Instructor 2

T₃ = Instructor 3

The subjects are assigned according to the expertise of the faculty members.

Table 02: Subject-Teacher Assignment of the Math Major Courses

Teacher	S1	S2	S3	S4	S5	S6	S7	S8	S9	S10
T1	0	1	0	0	1	0	0	0	1	0
T2	0	0	1	0	0	0	1	0	0	1
T3	1	0	0	1	0	1	0	1	0	0

The figure below shows the bipartite graph of the Subject-Teacher assignment:

Figure 01: Bipartite Graph of Subject-Teacher Assignment

In converting the edges of the bipartite graph into a vertex coloring problem, it will be converted into a line graph. The ten edges in Figure 1 acts as the vertices of the graph. The new set of variables are the following: T₁andS₂ = V₁ T₁andS₅ = V₂ T₁andS₉ = V₃ T₂andS₃ = V₄ T₂andS₇ = V₅ T₂andS₁0 = V₆ T₃andS₁ = V₇ T₃andS₄ = V₈ T₃andS₆ = V₉ T₃andS₈ = V₁₀. In consideration of the constraints, Table 02 shows the adjacency matrix of the vertices:

Table 03: Adjacency Matrix of the Vertices

Vertex	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10
V1	0	1	1	0	0	0	1	0	0	0
V2	1	0	1	1	0	0	0	1	1	0
V3	1	1	0	0	1	1	0	0	0	1
V4	0	1	0	0	1	1	0	1	1	0
V5	0	0	1	1	0	1	0	0	0	1
V6	0	0	1	1	1	0	0	0	0	1
V7	1	0	0	0	0	0	0	1	1	1
V8	0	1	0	1	0	0	1	0	1	1
V9	0	1	0	1	0	0	1	1	0	1
V10	0	0	1	0	1	1	1	1	1	0

Given the list of courses along with the set of potential conflicts, we can create a conflict-free timetable of courses by transforming Table 02 to the corresponding conflict graph G in Figure 02, and finding a minimum coloring. A vertex in G represents a course, an edge represents a pair of courses that conflict, and a color represents the period in which that particular course is to be scheduled.

Figure 02: Conflict Graph of the Adjacency Matrix

After applying graph coloring algorithm, the resultant graph in Figure 03 is properly colored with chromatic number 5. This is the minimum number of non-conflicting time-slots scheduling all the given courses [24].

Figure 03: Resultant Graph After Applying Graph Coloring Method

Table 04: Graph Coloring Solution of the Vertices and Period Allocation

1.Red	2.Blue	3.Green	4.Orange	5.Purple
(8:00-9:00	(9:00-10:00	(10:00-11:00	(8:00-9:30	(9:30-11:00
MWF)	MWF)	MWF)	TTh)	TTh)
V1	V2	V3	V9	V10
V5	V6	V4
V8	V7

The following table summarizes the solution to the timetable scheduling.

Table 05: Summary of the Class Timetable Schedule

Subject	Teacher	Period/Timeslot	Room
Math 101: History of Mathematics	Instructor 3	9:00-10:00 MWF	Room 2
Math 102: College and Advanced Algebra	Instructor 1	8:00-9:00 MWF	Room 2
Math 107: Calculus I with Analytic Geometry	Instructor2	10:00-11:00 MWF	Room 3
Math 105: Logic and Set Theory	Instructor 3	8:00-9:00 MWF	Room 3
Math 106: Elementary Statistics and Probability	Instructor 1	9:00-10:00 MWF	Room 3
Math 111: Modern Geometry	Instructor 3	8:00-9:30 TTh	Room 3
Math 109: Calculus III	Instructor 2	8:00-9:00 MWF	Room 5
Math 114: Linear Algebra	Instructor 3	9:30-11:00 TTh	Room 5
Math 115: Advanced Statistics	Instructor 1	10:00-11:00 MWF	Room 5
Math 119: Research in Mathematics	Instructor 2	9:00-10:00 MWF	Room 5

According to the resulting timeslots, subjects can be assigned into time periods in the timetables of first year, second year, and third year students while satisfying teachers’ and students’ constraints [25]. Table 04, Table 05, and Table 06 psresent conflict-free timetables, respectively.

Table 06: First year timetable

Table 07: second year timetable

Table 08: Third year timetable

The following tables present the conflict-free timetables for the Math Instructors in the department.

Table 09: Instructor 1 timetable

Table 10: instructor 2 timetable

Table 11: instructor 3 timetable

4. CONCLUSION

One of the most prevalent academic scheduling challenges in any educational system is timetable generation. The large number of students and courses offered complicates the task of scheduling classes within a limited time frame. An effective schedule must utilize resources such as subjects, teachers, students, and classrooms to avoid conflicts and satisfy various constraints. Graph coloring is an algorithmic approach that can address timetable scheduling by accommodating changing requirements, evolving subject demands, and their combinations. This study applied graph coloring to schedule major math courses for the Bachelor of Secondary Education Major in Mathematics for the first semester and to properly color the course conflict graph and translate this coloring into conflict-free timeslots. The course conflicted graph is constructed with teacher-subject pairs as nodes, and edges are drawn between conflicting courses, defined by those with common students. The complexity of scheduling problems escalates with the number and nature of constraints involved, and there is no universal algorithm to address all such problems effectively. This study focused on a typical course scheduling issue within a university curriculum, where the primary concerns are achieving uniqueness and optimality in the schedules. Due to the same chromatic number, various solutions can be generated, leading to non-unique schedules. The dynamic and intricate nature of scheduling necessitates further research and experimentation, especially with large datasets and increasingly complex constraints. An ideal algorithm for this purpose would achieve several goals: it would evenly allocate resources across available time slots without conflicts, generate schedules that are both unique and optimized, and satisfy all hard constraints while maximizing the number of soft constraints met. The pursuit of such an algorithm represents a significant and ongoing area of research, given the evolving challenges and requirements of scheduling problems.

REFERENCES

1. Adajian, L. (1996). Teachers’ professional community and the teaching of mathematics. Dissertation Abstracts International, 56(08), 3038. Abstract retrieved June 13, 2006, from Proquest database.
2. Alan Henobiagon Albino (2024). The Effectiveness of the Self-Learning Module in Science 6 towards the Development of Interactive Learning Resources. Dinkum Journal of Social Innovations, 3(07):349-370.
3. An, S. (2001). A comparative study of mathematics programs in the U.S. and China: The pedagogical content knowledge of middle school mathematics teachers in the U.S. and China. Dissertation Abstracts International, 61(11), 4315.
4. Alperin, S. (2001). Teacher attitudes toward increased planning time. Masters Abstracts International, 39(01), 15.
5. Artzt, A., & Armour-Thomas, E. (1999). A cognitive model for examining teachers’ instructional practice in mathematics: A guide for facilitating teacher reflection [Electronic version]. Educational Studies in Mathematics, 40, 211-235.
6. Ausubel, D. (1960). The use of advance organizers in the learning and retention of meaningful verbal material. Journal of Educational Psychology, 51, 267-272.
7. Babbie, E. (1973). Survey research methods (2nd ed.). Belmont, CA: Wadsworth, Inc.
8. Banbury, J. (1998). An analysis of changes in teacher instructional practices under block scheduling in seven suburban high schools. Dissertation Abstracts International, 59(03).
9. Mary Ann I. Peñaredondo (2024). Culinary Arts Facilities & its Effect on Students’ Academic Performance: Basis for Plant & Facilities Improvement Plan. Dinkum Journal of Social Innovations, 3(07):388-399
10. Bauwens, J., Hourcade, J., & Friend, M. (1989). Cooperative teacher: A model for general and special education integration. Remedial and Special Education, 10(2), 17-22.
11. Baylor, A., & Kitsantas, A. (2001). Promoting instructional planning: An experiment. In C. Crawford et al. (Eds.), Proceedings of Society for Information Technology and Teacher Education International Conference 2001 (pp. 1044-1049). Chesapeake, VA: AACE.
12. Bell, E., & Bell, R. (1985). Writing and mathematical problem solving: Arguments in favor of synthesis. School Science and Mathematics, 85(3), 210-221.
13. Bias, K. (n.d.). Constructivism in the classroom. Retrieved June 19, 2006,
14. Blank, R. (2004). Data on enacted curriculum study: Summary of findings experimental design study of effectiveness of DEC Professional Development Model on urban middle schools. Washington, D.C.: Council of Chief State School Officers. (ERIC Document Reproduction Service No. ED484702)
15. Yadap Phuyal (2024). My Journey of Learning & Teaching Mathematics as An algorithmic & Conceptual Problem Solver. Dinkum Journal of Social Innovations, 3(07):436-441.
16. Baki Koyuncu, Mahmut Secir. Student Time Table By Using Graph Algoritm. Ankara Uni- versity Computer Engineering Department, 06500, Be¸sevler, Ankara, Turkey.
17. Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map, Annals of Mathematics, 14, pp. 42-46. (1912)
18. Bresina, J.: Heuristic-Biased Stochastic Sampling, Proceedings of the 13th National Confer- ence on Artificial Intelligence. pp. 271-278. (1996)
19. Burke, E.K., Elliman, D.G., and Weare, R.F.: A University Timetabling System Based on Graph Colouring and Constraint Manipulation.Journal of Research on Computing in Educa- tion, 27 ( 1), pp. 1-18.(1994)
20. Deo, N.: Graph theory with applications to engineering and computer science. Prentice Hall of India. (1990)
21. Ganguli, Runa. Roy, Siddharta.: A Study on Course Timetable Scheduling using Graph Col- oring Approach”. International Journal of Computational and Applied Mathematics. ISSN 1819-4966 Volume 12, Number 2 pp. 469-485. (2017)
22. Juny Geraldizo Patierez (2024). Effects of Learning Motivation and Engagement on the Academic Performance and Satisfaction of Senior High School Students. Dinkum Journal of Social Innovations, 3(05):251-266.
23. Kenneth, A., and Wolfgang, H.: Every Planar Map is Four Colorable. I. Discharging. Illinois Journal of Mathematics, 21 (3), pp. 429–490. (1977).
24. Miner, S.K., Elmohamed, S., and Yau, H.W.: Optimizing Timetabling Solutions using Graph Coloring. NPAC, Syracuse University, pp. 99-106. (1995).