In this survey paper we present a general framework for coloring problems that was introduced in a joint paper which the author presented at WG2003. We show how a number of different types of coloring problems, most of which have been motivated from frequency assignment, fit into this framework. We give a survey of the existing results, mainly based on and strongly biased by joint work of the author with several different groups of coauthors, include some new results, and discuss several open problems for each of the variants.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||14|
|Publication status||Published - 2003|
|Publisher||Department of Applied Mathematics, University of Twente|
- Graph coloring
- Graph partitioning
- Forbidden subgraph
- Planar graph
- Computational complexity
Broersma, H. J. (2003). A general framework for coloring problems: old results, new results, and open problems. (Memorandum; No. 1704). Enschede: University of Twente, Department of Applied Mathematics.