Mixed graph edge coloring

Furmańczyk, Hanna; Kosowski, Adrian; Ries, Bernard; Żyliński, Paweł

doi:10.1016/j.disc.2008.11.033

Back

Journal article

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

2009

Published in:

Discrete Mathematics. - 2009, vol. 309, no. 12, p. 4027-4036

Theoretical Computer Science

Discrete Mathematics and Combinatorics

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