Kritischer Graph

Datei:4-critical graph.png

Ein Beispiel für einen 4-kritischen Graphen. Seine chromatische Zahl ist 4, aber alle seine richtigen Untergraphen haben eine chromatische Zahl kleiner als 4.

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 <math> k\in K(G) </math> gilt:

<math>\chi^{\prime}(G-k) < \chi^{\prime}(G) </math>

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

Literatur

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

Weblinks

Commons: critical graph – Sammlung von Bildern, Videos und Audiodateien

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