Rainbow Edge Colouring of Digraphs

	Rainbow Edge Colouring of Digraphs
Journal of Algorithms and Computation
دوره 53، شماره 2، اسفند 2021، صفحه 165-172 اصل مقاله (278.31 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2021.85350
نویسنده
Mahdieh Hasheminezhad^*
Department of Computer Science, Combinatorial and Geometric Algorithms Lab,Yazd University, Yazd, Iran
چکیده
An edge coloring of a digraph $D$ is called a $P_3$-rainbow edge coloring if the edges of any directed path of $D$ with length 2 are colored with different colors. It is proved that for a $P_3$-rainbow edge coloring of a digraph $D$, at least $\left\lceil{log_2{\chi(D)}} \right\rceil$ colors are necessary and $ 2\left\lceil{log_2{\chi(D)}}\right\rceil\}$ colors are enough. One can determine in linear time if a digraph has a $P_3$-rainbow edge coloring with 1 or 2 colors. In this paper, it is proved that determining that a digraph has a $P_3$-rainbow edge coloring with 3 colors is an NP-complete problem even for planar digraphs. Moreover, it is shown that $\left\lceil{log_2{\chi(D)}}\right\rceil$ colors is necessary and sufficient for a $P_3$-rainbow edge coloring of a transitive orientation digraph $D$.
کلیدواژه‌ها
vertex equitable labeling؛ vertex rainbow coloring؛ planar digraphs؛ template-driven rainbow coloring؛ transitive digraph؛ dichromatic index

آمار تعداد مشاهده مقاله: 432 تعداد دریافت فایل اصل مقاله: 522

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب