Journal of Graph Theory · 1999 · 23 citations · 6 references
Natural SciencesComputer ScienceAlgorithmsColor TheoryCombinatoricsCombinatorial OptimizationDirected Acyclic GraphsGraph AlgorithmsGraph ColoringGraph TheoryEdge ColoringVertex Coloring
We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999
6
Choice Reviews Online · 1995 · 1.3K citations
Paths, Stars and the Number Three
Bruce Reed · Combinatorics Probability Computing · 1996 · 182 citations
On the arc-chromatic number of a digraph
S. Poljak, V. Rödl · Journal of Combinatorial Theory Series B · 1981 · 71 citations