Groupe d’études et de recherche en analyse des décisions

G-90-46

Bounded Vertex Colorings of Graphs

, et

A bounded vertex coloring of a graph G is a usual vertex coloring in which each color is used at most k times (where k is a given number). The bounded chromatic number k (G) of G is the smallest number of colors such that G admits a bounded coloring. Upper and lower bounds on k (G) are given in terms of k, the number n of vertices, the usual chromatic number (G) and the maximum degree (G) of G. Complexity of bounded vertex coloring is discussed and several classes of graphs for which this problem is polynomially solvable are identified.

, 13 pages

Ce cahier a été révisé en mai 1991