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

Datei:Commons-logo.svg

[{{canonicalurl:Commons:Category:{{#if:critical graph|critical graph|Kritischer Graph}}|uselang=de}} Commons: {{#if:|{{{2}}}|{{#if:critical graph|critical graph|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: critical graph

   | {{#ifeq: {{#invoke:Str|left|critical graph|9}} 
       | category: 

| }}}}

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