Multicoloring: Problems and Techniques

Abstract A multicoloring is an assignment where each vertex is assigned not just a single number (a “color”) but a set of numbers. The number of colors assigned to the vertex is specified by the length (or color requirement ) parameter of that vertex in the input. As usual, adjacent vertices cannot receive the same color; thus here, the sets of colors they receive must be disjoint. Multicolorings are therefore proper generalizations of ordinary graph colorings. The purpose of this paper is to summarize some of the techniques that have been developed specifically for obtaining good approximate multicolorings in different classes of graphs.

Authors

• Magnús M. Halldórsson
• Guy Kortsarz

Keywords

No keywords are indexed for this paper.