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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.