Kritischer Graph

Ein kritischer Graph ist ein Begriff aus der Graphentheorie, der 1965 vom Vadim G. Vizing zur Untersuchung von Kantenfärbungen eingeführt worden ist. Er beschreibt eine Sorte von Graphen, deren chromatischer Index sich durch das Entfernen einer beliebigen Kante immer verkleinert.

Definition

Ein schlichter zusammenhängender Klasse 2-Graph G heißt kritisch, falls für jede Kante $k\in K(G)$ gilt:

$\chi ^{\prime }(G-k)<\chi ^{\prime }(G)$

Hierbei bezeichnet $\chi ^{\prime }$ den chromatischen Index eines Graphen und ein Klasse 2-Graph einen Graphen, dessen chromatischer Index größer ist als sein Maximalgrad ( $\chi ^{\prime }(G)>\Delta (G)$ ).

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 292ff

Weblinks

• Lutz Volkmann: Graphen an allen Ecken und Kanten (PDF; 3,5 MB), Skript 2006, S. 244ff