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 oil the number of required colors and analyze the complexity Status of this problem. In particular, we provide N P-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. (C) 2008 Elsevier B.V. All rights reserved.


Published in:
Discrete Mathematics, 309, 4027-4036
Year:
2009
Publisher:
Elsevier
ISSN:
0012-365X
Keywords:
Laboratories:




 Record created 2012-01-09, last modified 2018-03-18


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)