Der chromatische Index (auch Kantenfärbungszahl) ist in der Graphentheorie die kleinste Anzahl von Farben, mit der sich die Kanten eines Graphen färben lassen, ohne dass zwei an einem Knoten anliegenden Kanten die selbe Farbe bekommen. Der chromatische Index eines Graphen entspricht entweder seinem Maximalgrad oder ist um eins höher als dieser. Die Graphen des ersten Falles werden auch als class one und im zweiten Fall als class two bezeichnet.

Das Problem, den chromatischen Index eines beliebigen Graphen zu bestimmen, ist im allgemeinen Fall NP-schwer. Dies gilt auch für die Einschränkung auf reguläre Graphen. Bipartite Graphen sind immer class one.

Siehe auch

• Chromatische Zahl (Knotenfärbungszahl), Färbung von Graphen