Graph theory - chromatic index

Question

I have to make a program which will say if graph is d colorable or not - basically i have to check if chromatic index is d or d+1, where d is max degree of all vertices (vizing's theorem). I know this problem is NP-complete and basically it has to be bruteforced. I had an idea but don't know if it is correct -

1) find vertex with deg(v) = d and color all edges incident with v with d distnict colors.

2) for all edges incident with vertices which are adjacent to v, apply some color from set of d colors

3) repeat 2) for "discovered" edges

If all edges are colored with d colors, chromatic index is d and i have one coloring of graph G.

If some edge can't be colored with color from set of d colors, color him with d+1-st color and color remaining edges with colors from set of d+1 colors - here is the question - using this scheme, if i proclaim that chromatic index to be d+1, is there a chance that with some other coloring chromatic index would be d? (for every edge that is going to be colored I'm choosing one color which can be used)..

Also, which graph representation would be best for this problem? In input file graph is written in adjacency matrix. i know it can be solved with recursion, but I don't have an idea how. I'm stuck with some too complicated ideas :S (some hint or pseudocode would be appreciated).

Edit:

Just came across my mind, I think it should be ok (pure bruteforce). I didnt try to implement this yet. Please comment if you see something wrong. Just to say again - algorithm should check whether graph is edge colorable with d or d+1 colors where d is max degree of all vertices in given simple graph, and to find one coloring...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding 
        //coloring with d+1 colors
        extra = true; 
        color it in color extra;
    }

    //recursivly try to color adjacent edges with available colors
    for each color c' from set of d colors {
        for each edge k adjacent to current {
            colorE(k, c', extra)
        }
    }
}

//main
bool extra = false;
for each color b from set of d colors {
    colorEdge(some starting edge, b, extra)
    if (!extra) break;
}

Answer 1

Generate constraints for each edge, assign different colours to all edges of the vertex with the most edges and then process each edges from the most constrained edge.

for each edge e1
for each edge e2
  if (e1 and e2 have a common vertex)
    e1.addConstaint(can't match e2's colour)
    e2.addConstaint(can't match e1's colour)

vertex v = vertex with most edges
if (v has more edges than colours we have available) STOP
assign each edge of v a different colour

Sort edges by number of constraints
Remove all edges connected to v (thus assigned a colour)

process(edge) :=
  while (haven't tried all colours within the constraints)
    edge.colour = next untried colour within the constraints
    process(next most constrained edge)

process(most constrained edge)

It may be a good idea to defined the most constrained edge as the one with the most surrounding edges that have already been assigned colours, but this could cause quite a bit of overhead.