Klassifizierung (Graphentheorie)
# Klassifizierung (Graphentheorie)

Als Klassifizierung oder auch Klassifizierungsproblem bezeichnet man in der Graphentheorie die Zuordnung von Graphen zu einer der beiden wie folgt definierten Klassen:

    Klasse 1: Ein Multigraph G dessen Maximalgrad seinen chromatischen Index entspricht, d. h. $\chi ^{\prime }(G)=\Delta (G)$.
    Klasse 2: Ein Multigraph G dessen chromatischer Index größer ist als sein Maximalgrad ist, d. h. $\chi ^{\prime }(G)>\Delta (G)$.

Entsprechend seiner Zuordnung wird dann ein Graph dann auch als Klasse 1-Graph oder einen Klasse 2-Graph bezeichnet.

