Journal article

Mixed graph edge coloring

Show more…
    2009
Published in:
  • Discrete Mathematics. - 2009, vol. 309, no. 12, p. 4027-4036
English 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.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307878
Statistics

Document views: 3 File downloads:
  • mixededgecoloring.pdf: 1