|
|||||
|
|
Mixed graph edge coloring |
|
| Authors: | Hanna Furmańczyk Pawe? ?yliński |
| Institution: | a Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland b Department of Algorithms and System Modeling, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland c Institut de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, Station 8, 1015 Lausanne, Switzerland |
| Abstract: | 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. |
| Keywords: | Mixed graphs Complexity Precoloring extension Bipartite graphs Trees Edge coloring Network communication |
| 本文献已被 ScienceDirect 等数据库收录！ | |