|
On an Open Problem in Defective Graph Colourings |
|---|
Alewyn P Burger1, Paul JP Grobler2, Isabelle Nieuwoudt2 & Jan H van Vuuren1
Abstract
The Delta(d)-chromatic number of a graph G is the smallest number of colours with which the vertices of G may be coloured so that the maximum degree of each colour class induced subgraph of G is at most some fixed, non-negative integer d. The Delta(d)-chromatic sequence of a graph G is merely the sequence of Delta(d)-chromatic numbers of G as d increases from zero to infinity. A set of necessary conditions for a sequence of integers to be the Delta(d)-chromatic sequence of some graph is known. However, it is not known whether these necessary conditions are also sufficient conditions. In this paper a subset of essential sequences of the full set of sequences satisfying these necessary conditions is isolated and an attempt to answer the question of sufficiency is described.
An electronic version of the complete paper may be obtained here: [pdf].
Affiliations
1 Department of Logistics, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa, emails: apburger@sun.ac.za and vuuren@sun.ac.za.
2 Applied Mathematics Division, Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland, 7602,
Republic of South Africa, emails: pgrobler@sun.ac.za and isabelle@sun.ac.za.