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.


Publié dans:
Discrete Mathematics, 309, 4027-4036
Année
2009
Publisher:
Elsevier
ISSN:
0012-365X
Mots-clefs:
Laboratoires:




 Notice créée le 2012-01-09, modifiée le 2019-12-05


Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)