Graphentheorie - chromatischer Index

Ich muss ein Programm machen, das sagt, ob der Graph d-färbbar ist oder nicht - im Grunde muss ich prüfen, ob der chromatische Index d oder d + 1 ist, wobei d der maximale Grad aller Ecken ist (Satz von vizing). Ich weiß, dass dieses Problem NP-vollständig ist und im Grunde muss es bruteed sein. Ich hatte eine Idee, weiß aber nicht, ob es richtig ist -

1) Finde den Scheitelpunkt mit deg (v) = d und fülle alle Kanten, die mit v auffallen, mit d Farben ab.

2) Für alle Kanten, die mit Ecken kollidieren, die an v angrenzen, wird eine Farbe aus dem Satz von d Farben angewendet

3) wiederhole 2) für "entdeckte" Kanten

Wenn alle Kanten mit d Farben gefärbt sind, ist der chromatische Index d und ich habe eine Färbung des Graphen G.

Wenn einige Kanten nicht mit Farben aus d-Farben gefärbt werden können, färben Sie ihn mit d + 1-st Farbe und färben Sie die restlichen Kanten mit Farben aus d + 1 Farben - hier ist die Frage - mit diesem Schema , wenn ich diesen chromatischen Index zu d + 1 proklamiere, besteht die Möglichkeit, dass bei einem anderen Farbwert der chromatische Index d wäre? (Für jede Kante, die farbig sein soll, wähle ich eine Farbe, die verwendet werden kann).

Welche Graphdarstellung wäre für dieses Problem am besten geeignet? In der Eingabedatei wird der Graph in die Adjazenzmatrix geschrieben. Ich weiß, dass es mit Rekursion gelöst werden kann, aber ich habe keine Idee wie. Ich stecke mit ein paar zu komplizierten Ideen fest: S (ein Hinweis oder Pseudocode wäre wünschenswert).

Bearbeiten:

Mir ist gerade in den Sinn gekommen, ich denke, es sollte in Ordnung sein (reine Bruteforce). Ich habe das noch nicht versucht. Bitte kommentieren Sie, wenn Sie etwas falsch sehen. Nur um es noch einmal zu sagen - der Algorithmus sollte prüfen, ob der Graph edge-färbbar mit d oder d + 1 Farben ist, wobei d der maximale Grad aller Ecken in einem gegebenen einfachen Graph ist, und um eine Färbung zu finden ...