Furmańczyk, Hanna Kosowski, Adrian Ries, Bernard Żyliński, Paweł 2009 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 NP-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. application/pdf https://sonar.ch/global/documents/307878 https://sonar.ch/documents/307878/files/mixededgecoloring.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.disc.2008.11.033 info:eu-repo/semantics/openAccess License undefined Discrete Mathematics. - 2009, vol. 309, no. 12, p. 4027-4036 Theoretical Computer Science Discrete Mathematics and Combinatorics info:eu-repo/classification/udc/004 Mixed graph edge coloring http://purl.org/coar/resource_type/c_6501