Klassifizierung (Graphentheorie)
(Weitergeleitet von Klasse 1-Graph)
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. <math>\chi^{\prime}(G)=\Delta(G)</math>.
- Klasse 2: Ein Multigraph G dessen chromatischer Index größer ist als sein Maximalgrad ist, d. h. <math>\chi^{\prime}(G)>\Delta(G)</math>.
Entsprechend seiner Zuordnung wird dann ein Graph dann auch als Klasse 1-Graph oder einen Klasse 2-Graph bezeichnet.
Literatur
- Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 289, 299ff
Weblinks
- Lutz Volkmann: Graphen an allen Ecken und Kanten (PDF-Datei; 3,51 MB). Skript 2006, S. 242, 250ff