Contrast in greyscales of graphs

Natalia Castro (), María A. Garrido-Vizuete (), Rafael Robles () and María Trinidad Villar-Liñán ()
Additional contact information
Natalia Castro: Universidad de Sevilla
María A. Garrido-Vizuete: Universidad de Sevilla
Rafael Robles: Universidad de Sevilla
María Trinidad Villar-Liñán: Universidad de Sevilla

Journal of Combinatorial Optimization, 2020, vol. 39, issue 3, No 13, 874-898

Abstract: Abstract In this paper, we present the notion of greyscale of a graph, as a colouring of its vertices that uses colours from the continuous spectrum [0, 1]. Any greyscale induces another colouring by assigning to each edge the non-negative difference between the colours of its vertices. These edge colours are ordered in lexicographical increasing order and make up the contrast vector of the greyscale. The aim of the contrast problem for the given graph is to find the maximum contrast vector and the greyscales that give rise to it, namely the maximum contrast greyscales. The NP-completeness of this problem is stated by means of a functional relation between the chromatic number and the first component of the maximum contrast vector, named the lightest tone. Thus, we introduce the notion of lightest tone as a new invariant of the graph. The underlying structure of values of maximum contrast greyscales is addressed and we prove that they are linked by rational number sets, which are algorithmically determined. The restricted maximum contrast problem, that is, greyscales with prefixed extreme tones, is also defined and solved in polynomial time for different families of bipartite graphs.

Keywords: Graph colouring; Greyscale; Maximum contrast; NP-completeness; Primary 05C; 68R; Secondary 05C15; 05C85; 90C47 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00528-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:3:d:10.1007_s10878-020-00528-w

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00528-w

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().