پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,228 |
| تعداد مقالات | 67,750 |
| تعداد مشاهده مقاله | 115,080,526 |
| تعداد دریافت فایل اصل مقاله | 89,818,871 |
Pointed Conflict-Free Colouring of Digraphs | ||
| Journal of Algorithms and Computation | ||
| مقاله 7، دوره 50، شماره 1، شهریور 2018، صفحه 119-131 اصل مقاله (254.46 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2018.68425 | ||
| نویسنده | ||
| Mahdieh Hasheminezhad* | ||
| Yazd university | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| conflict-free colouring؛ hypergraph؛ digraph؛ dynamic colouring | ||
|
آمار تعداد مشاهده مقاله: 195 تعداد دریافت فایل اصل مقاله: 200 |
||