On Minimum Entropy Graph Colorings

Abstract — We study properties of graph colorings that minimize the quantity of color information with respect to a given probability distribution on the vertices. The minimum entropy of any coloring is the chromatic entropy. Applications of the chromatic entropy are found in coding with side information and digital image partition coding. We show that minimum entropy colorings are hard to compute even if a minimum cardinality coloring is given, the distribution is uniform, and the graph is planar. We also consider the minimum number of colors in a minimum entropy coloring, and show that this number can be arbitrarily larger than the chromatic number, even for restricted families of uniformly weighted graphs. I. Definitions A coloring of a graph G is an assignment of colors to the vertices of G such that any two adjacent vertices have different colors. The well-known graph coloring problem is to find a coloring with as few colors as possible. The minimum number of colors in a coloring of G is the chromatic number of G, denoted by χ(G). A probabilistic graph is a graph equipped with a probability distribution on its vertices. Let (G, P) be a probabilistic graph, and let X be any random variable over the vertex set V (G) of G with distribution P. We define the entropy of a coloring φ as the entropy of the random variable φ(X). In other words, the entropy of φ is the sum over all colors i of −pi log pi, where pi = � x:φ(x)=i P (x) is the probability that X has color i. The chromatic entropy Hχ(G, P) of the probabilistic graph (G, P) is the minimum entropy of any of its colorings. It was first defined by Alon and Orlistky [3] and gives the minimum quantity of color information contained in any coloring of a probabilistic graph. Applications of this definition can be found in zero-error source coding with side information at the receiver [3, 5, 6], and compression of digital image partitions created by segmentation algorithms [1, 2]. In fact, minimum entropy colorings of a characteristic graph directly induce good codes for the two problems