Critical graph

A critical graph is a term from graph theory that was introduced in 1965 by Vadim G. Vizing to investigate edge coloring . It describes a kind of graph, the chromatic index of which decreases by removing any edge.

definition

A simple connected class 2 graph G is called critical if for every edge : ${\displaystyle k\in K(G)}$

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

Here, the chromatic index of a graph and a class 2 graph denotes a graph whose chromatic index is greater than its maximum degree ( ). ${\displaystyle \chi ^{\prime }}$ ${\displaystyle \chi ^{\prime }(G)>\Delta (G)}$

literature

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

Web links

• Lutz Volkmann: Graphs on all corners and edges (PDF; 3.7 MB) , script 2006, p. 244ff