On the maximum degree chromatic number of a graph

[摘要] ENGLISH ABSTRACT:Determining the (classical) chromatic number of a graph (i.e. finding the smallest number of colours withwhich the vertices of a graph may be coloured so that no two adjacent vertices receive the same colour)is a well known combinatorial optimization problem and is widely encountered in scheduling problems.Since the late 1960s the notion of the chromatic number has been generalized in several ways by relaxingthe restriction of independence of the colour classes.

[发布机构] Stellenbosch University