On the(d)–chromatic number of a complete balanced multipartite graph
Date
2007
Journal Title
Journal ISSN
Volume Title
Publisher
Operations Research Society of South Africa
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 integer d 2 N. The minimum number of colours in such a
colouring is referred to as the (d)–chromatic number of G. The problem of finding
the (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 some shared resource. These conflicts are represented by edges in a so–called
resource access graph, where vertices represent the users. An efficient resource access
schedule is an assignment of the users to a minimum number of groups (modelled by
means of colour classes) where some threshold d 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 (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).
Description
CITATION: Burger, A. P., Nieuwoudt, I. & Van Vuuren, J.H. 2007. On the(d)–chromatic number of a complete balanced multipartite graph. ORiON, 23(1):29-49, doi:10.5784/23-1-45.
The original publication is available at http://orion.journals.ac.za
The original publication is available at http://orion.journals.ac.za
Keywords
Graphs -- Maximum degree, Graph colouring, Graph theory
Citation
Burger, A. P., Nieuwoudt, I. & Van Vuuren, J.H. 2007. On the(d)–chromatic number of a complete balanced multipartite graph. ORiON, 23(1):29-49, doi:10.5784/23-1-45