Contrast in greyscales of graphs 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,xc2xa01. Any greyscale induces another colouring by assigning to each edge the nonnegative 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 NPcompleteness 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.

Complexity of Restricted Variant of Star Colouring. Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For ( kin mathbb N ), a ( k )restricted star (( k )rs) colouring of a graph ( G ) is a function ( f:V(G)rightarrow 0,1,dots ,k,,1 ) such that (i) ( f(x)ne f(y) ) for every edge ( xy ) of ( G ), and (ii) there is no bicoloured 3vertex path(( P_3 )) in ( G ) with the higher colour on its middle vertex. We show that for ( kge 3 ), it is NPcomplete to decide whether a given planar bipartite graph of maximum degree ( k ) and girth at least six is ( k )rs colourable, and thereby answer a problem posed by Shalu and Sandhya (Graphs and Combinatorics 2016). In addition, we design an ( O(n3) ) algorithm to test whether a chordal graph is 3rs colourable.