Paper Info
Title
Parameterized Mixed Graph Coloring
Abstract
Coloring of mixed graphs that contain both directed arcs and undirected edges is relevant for scheduling of unit-length jobs with precedence constraints and conflicts. The classic GHRV theorem (attributed to Gallai, Hasse, Roy, and Vitaver) relates graph coloring to longest paths. It can be extended to mixed graphs. In the present paper we further extend the GHRV theorem to weighted mixed graphs. As a byproduct this yields a kernel and a parameterized algorithm (with the number of undirected edges as parameter) that is slightly faster than the brute-force algorithm. The parameter is natural since the directed version is polynomial whereas the undirected version is NP-complete. Furthermore we point out a new polynomial case where the edges form a clique.
Year
DOI
Venue
2019
10.1007/s10878-019-00388-z
Journal of Combinatorial Optimization
Keywords
Field
DocType
Graph coloring, Mixed graph, Scheduling, Longest path, Parameterized algorithm
Kernel (linear algebra),Combinatorics,Parameterized complexity,Polynomial,Clique,Scheduling (computing),Mixed graph,Longest path problem,Mathematics,Graph coloring
Journal
Volume
Issue
ISSN
38.0
2.0
1573-2886
Citations 
PageRank 
References 
0
0.34
0
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99