• Home
  • Browse
    • Current Issue
    • By Issue
    • By Author
    • By Subject
    • Author Index
    • Keyword Index
  • Journal Info
    • About Journal
    • Aims and Scope
    • Editorial Board
    • Editorial Staff
    • Publication Ethics
    • Indexing and Abstracting
    • Related Links
    • FAQ
    • Peer Review Process
    • News
  • Guide for Authors
  • Submit Manuscript
  • Reviewers
  • Contact Us
 
  • Login
  • Register
Home Articles List Article Information
  • Save Records
  • |
  • Printable Version
  • |
  • Recommend
  • |
  • How to cite Export to
    RIS EndNote BibTeX APA MLA Harvard Vancouver
  • |
  • Share Share
    CiteULike Mendeley Facebook Google LinkedIn Twitter
Journal of Algorithms and Computation
Articles in Press
Current Issue
Journal Archive
Volume Volume 51 (2019)
Volume Volume 50 (2018)
Issue issue 2
Summer and Autumn 2018
Issue Issue 1
June 2018
Volume Volume 49 (2017)
Volume Volume 48 (2016)
Volume Volume 47 (2016)
Volume Volume 46 (2015)
Volume Volume 45 (2014)
Volume Volume 44 (2013)
Volume Volume 43 (2009)
Volume Volume 42 (2008)
Volume Volume 41 (2007)
Hasheminezhad, M. (2018). Pointed Conflict-Free Colouring of Digraphs. Journal of Algorithms and Computation, 50(1), 119-131.
Mahdieh Hasheminezhad. "Pointed Conflict-Free Colouring of Digraphs". Journal of Algorithms and Computation, 50, 1, 2018, 119-131.
Hasheminezhad, M. (2018). 'Pointed Conflict-Free Colouring of Digraphs', Journal of Algorithms and Computation, 50(1), pp. 119-131.
Hasheminezhad, M. Pointed Conflict-Free Colouring of Digraphs. Journal of Algorithms and Computation, 2018; 50(1): 119-131.

Pointed Conflict-Free Colouring of Digraphs

Article 7, Volume 50, Issue 1, June 2018, Page 119-131  XML PDF (254.46 K)
Document Type: Research Paper
Author
Mahdieh Hasheminezhad email
Yazd university
Abstract
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.
Keywords
conflict-free colouring; hypergraph; digraph; dynamic colouring
Statistics
Article View: 51
PDF Download: 54
Home | Glossary | News | Aims and Scope | Sitemap
Top Top

This work is licensed under a Creative Commons Attribution 4.0 International License
Journal Management System. Designed by sinaweb.