On the Delta(d)-chromatic number of a complete balanced multipartite graph

Alewyn P Burger¹, Isabelle Nieuwoudt² & Jan H van Vuuren³

Abstract

In this paper we solve (approximately) the problem of finding the minimum number of colours with which the vertices of a complete, balanced, multipartite graph G may be coloured such that the maximum degrees of all colour class induced subgraphs are at most some specified natural number d. The minimum number of colours in such a colouring is referred to as the Delta(d)-chromatic number of G. The problem of finding the Delta(d)-chromatic number of a complete, balanced, multipartite graph has its roots in an open graph theoretic characterisation problem and has applications conforming to the generic scenario where users of a system are in conflict if they require access to one or more of the same resources. These conflicts are represented by edges in a so-called resource access graph, where vertices represent the users. An effcient resource access schedule is an assignment of the users to a minimum number of groups (modelled by means of colour classes) where some threshold of of conflict may be tolerated in each group. If different colours are associated with different time periods in the schedule, then the minimum number of groupings in an optimal resource access schedule for the above set of users, is given by the Delta(d)-chromatic number of the resource access graph. A complete balanced multipartite resource access graph represents a situation of maximum conflict between members of different user groups of the system, but where no conflict occurs between members of the same user group (perhaps due to an allocation of diverse duties to the group members).

An electronic version of the complete paper may be obtained here: [pdf].

Affiliations

¹ Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, Email.

² Applied Mathematics Division, Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, Email.

² Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, Email.

Home