Classification (graph theory)

As a classification or classification problem is known in the graph theory the assignment of graphs into one of two classes defined as follows:

Class 1 : A multigraph G whose maximum degree corresponds to its chromatic index , ie . ${\displaystyle \chi ^{\prime }(G)=\Delta (G)}$

Class 2 : A multigraph G whose chromatic index is greater than its maximum degree, ie . ${\displaystyle \chi ^{\prime }(G)>\Delta (G)}$

Depending on its assignment, a graph is then also referred to as a class 1 graph or a class 2 graph .

literature

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

Web links

• Lutz Volkmann: Graphs on all corners and edges (PDF file; 3.51 MB) . Script 2006, p. 242, 250ff