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.

On the Complexity of Digraph Colourings and Vertex Arboricity It has been shown by Bokal et al. that deciding 2colourability of  :12,an NPcomplete problem. This result was later on extended by Feder et al.  that deciding :26,whether a digraph has a circular pcolouring  :36,91,110,131,for all rational pu003e1. In this paper, we consider the  :47,corresponding decision problems :36,91,110,131,for related notions of fractional  :56,digraphs and graphs, including the star dichromatic number, the  :66,number and the circular vertex arboricity. We prove the   :76,Deciding if the star dichromatic :66,number of a digraph is at most p  :36,91,110,131,for every rational   :76,Deciding if the fractional dichromatic :66,number of a digraph is at most p  :36,91,110,131,for every :95,135,pu003e1, p neq   :76,Deciding if the circular vertex :116,arboricity of a graph is at most p  :36,91,110,131,for every rational   To show these results, different techniques are required in each case.  :148,to prove the first result, we relate the star dichromatic :66,number :148,to a  of :162,homomorphisms between digraphs, called circular homomorphisms,  :170,be of independent interest. We provide a classification of  :180,complexities of the :47,corresponding homomorphism colouring  :148,to the :187,one derived by Feder et al. :36,91,110,131,for acyclic homomorphisms.