کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649338 1342450 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Mixed graph edge coloring
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Mixed graph edge coloring
چکیده انگلیسی

We are interested in coloring the edges of a mixed graph, i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds on the number of required colors and analyze the complexity status of this problem. In particular, we provide NPNP-completeness results for the case of outerplanar graphs, as well as for 3-regular bipartite graphs (even when only 3 colors are allowed, or when 5 colors are allowed and the graph is fully oriented). Special cases admitting polynomial-time solutions are also discussed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 12, 28 June 2009, Pages 4027–4036
نویسندگان
, , , ,