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.
Hasheminezhad, M. (2018). Pointed Conflict-Free Colouring of Digraphs. Journal of Algorithms and Computation, 50(1), 119-131. doi: 10.22059/jac.2018.68425
MLA
Mahdieh Hasheminezhad. "Pointed Conflict-Free Colouring of Digraphs". Journal of Algorithms and Computation, 50, 1, 2018, 119-131. doi: 10.22059/jac.2018.68425
HARVARD
Hasheminezhad, M. (2018). 'Pointed Conflict-Free Colouring of Digraphs', Journal of Algorithms and Computation, 50(1), pp. 119-131. doi: 10.22059/jac.2018.68425
VANCOUVER
Hasheminezhad, M. Pointed Conflict-Free Colouring of Digraphs. Journal of Algorithms and Computation, 2018; 50(1): 119-131. doi: 10.22059/jac.2018.68425
)