2
$\begingroup$

I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.

Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the edges with the minimum number of colours required so that in-going edges at a vertex must be a different colours and out going edges at a vertex must be a different colours, but an out going edge and an in going edge at a vertex may share a colour.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Minimal number of colours always equals maximum in- or out- degrees. It clearly can not be less, if this maximum equals $d$, we show how to colour all edges in colours $1,\dots,d$. At first, we add some new vertices and new edges so that all indegrees and outdegrees are equal to $d$. This is possible by many ways.

Next, we assign to each vertex a boy and a girl and say that for any directed edge $xy$ a boy $B(x)$ in a vertex $x$ knows a girl $G(y)$ in $y$. Then our bipartite boys-girls graph has all degrees equal to $d$. It is known that such a graph is a union of $d$ disjoint perfect matchings. These are our colours.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, i realised an hour after posting it is just bipartite matching, we can map each oriented edge from $x$ to $y$ as an edge in bipartite graph from vertex $x$ in $A$ to vertex $y$ in $B$, but thanks anyway $\endgroup$
    – Pavan Sangha
    Commented Feb 27, 2016 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .