Contrast in Greyscales of Graphs

Abstract

A greyscale $f$ of a graph $G(V,E)$ is a mapping from $V$ to the interval $[0,1]$ such that $\{0,1\}\subseteq Im(f)$. This function $f$ induces another mapping $\hat{f}$ on $E$ by assigning to each edge the non-negative difference of the values of $f$ on its vertices. The contrast vector $cont(G,f)$ is defined as the vector $(\hat{f}(e_1),\hat{f}(e_2),\dots ,\hat{f}(e_m))$ for all edges $e_i$ of $G$ in such a way that $\hat{f}(e_i)\le \hat{f}(e_{i+1})$ for $i=1,2,\dots ,m-1$. The concept of maximum contrast vector is presented by using the lexicographical ordering in the set of contrast vectors of all possible greyscales defined on $G$ and a greyscale that gives rise to a maximum contrast vector is named maximum contrast greyscale. The relation between finding the maximum contrast vector for the graph $G$ and the chromatic number of $G$ is established. Thus the maximum contrast problem is an NP-complete problem. However, the set of values of any maximum contrast greyscale for any graph is bounded by a finite set which is given. Several methods to compute the maximum contrast vector with some restrictions in are collected in this paper.

29 pages, 4 figures, one table. Linked data document to this paper can be found in https://www.researchgate.net/publication/311576608_FksetsContrast