1967/01/01 by Dominic Welsh · 4 citations
Decision Sciences · Engineering · Mathematics · #Scheduling and Timetabling Solutions #Scheduling and Optimization Algorithms #Combinatorics #Upper and lower bounds #Graph #Chromatic scale #Wheel graph #Mathematics #Strength of a graph #Graph power #Computer science #Line graph
paper · pdf · doi:10.1093/comjnl/10.1.85
openalex publication_date 1967/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
This paper points out the connection between the basic scheduling or timetabling problem with the well known problem of colouring the vertices of a graph in such a way that (i) no two adjacent vertices are the same colour and (ii) the number of colours used is a minimum. We give an algorithm for colouring a graph subject to (i) and give a new easily determined bound for the number of colours needed. This same bound is also a new upper bound for the chromatic number of a graph in terms of the degrees of its vertices.