Well... since the graph is loopless I'd imagine you can use some kind of recursive algorithm since you won't visit the same node twice.
Start at some random node and branch out to the rest of the graph. If your start node has N edges, color them 1 - N, and generate N recursive calls that pass along the color (C) of the edge to the node connected to that edge. That node may therefore start again with 1 - N, coloring edges connected to it going outward, excluding the color C of the incoming edge.
This would never work if the graph had loops. It also only works in a fully connected graph. But it should work, off the top of my head, in a loopless connected graph.
Additionally, you would want to assign nodes and edges a unique ID number for the purposes of keeping track of incoming and outgoing edges to each node.
Recursive call might look like....
color_graph(incomingEdge, incomingColor, currentNode).
Where initially you begin with color_graph(NULL, NULL, startNode).
And for each node you would want to do something like
Code:
int rval=0;
for (c = 0; c < numEdges(currentNode) - 1; c++)
{
nextEdge = getNextEdge(currentNode);
nextNode = getNextNode(nextEdge);
if (c != incomingColor) rval=color_graph(nextEdge, c, nextNode);
else rval=color_graph(nextEdge, numEdges(currentNode), nextNode);
}
if (rval > c) return rval;
else return c;
Now, I don't know if this logic is 100% yet, but it should work. rval would be returning the maximum encountered value of k (color).
In short though, the 'cheating' way to do this is to realize that k can never be smaller than the number of edges going into any one node. Therefore, the node with the most edges determines the minimal value of k.
Help me an algorithm 
Linear Mode
