Abstract :
In a pointed confl
ict-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 nd a PCFP colouring with a minimum
number of colours and for a given tree, one can nd 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
nding 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.
