Mixed graph edge coloring
-
Furmańczyk, Hanna
University of Gdansk, Gdansk, Poland
-
Kosowski, Adrian
Gdansk University of Technology, Gdansk, Poland
-
Ries, Bernard
EPFL, Lausanne, Switzerland
-
Żyliński, Paweł
University of Gdansk, Gdansk, Poland
Show more…
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 et du management
-
Department
- Département d'informatique
-
Language
-
-
Classification
-
Computer science and technology
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/307878
Statistics
Document views: 36
File downloads:
- mixededgecoloring.pdf: 67