Pointed Conflict-Free Colouring of Digraphs

In a pointed conflict-free partial   (PCFP) colouring of a digraph, each vertex has at least  one in-neighbour with unique colour.  In this paper,  it is proved that PCFP k-colourability of digraphs is NP-complete,  for any k >0.  Nevertheless  for   paths and cycles, one can  in linear time  find  a PCFP colouring  with a minimum number of colours and for a given tree, one can find a PCFP 2-colouring. In this paper a bipartite digraph  whose arcs start from the same part is called  a one-way bipartite digraph. It is proved every one-way bipartite  planar digraph has a PCFP 6-colouring,  every one-way bipartite planar digraph whose each vertex  has in-degree zero or greater than one, has a  PCFP 5-colouring and  every one-way bipartite planar digraph whose each vertex  has in-degree zero or greater than two, has a  PCFP 2-colouring. Two simple algorithms are proposed for finding a  PCFP colouring of a given digraph  such that the number of colours used is not  more than the maximum out-degree of  the vertices. For a digraph with a given PCFP colouring,  it is shown how to recolour the vertices after vertex or arc insertion or deletion to obtain a PCFP colouring for the new digraph.