DM2

Eine Menge von Knoten, zwischen denen keine Kanten existieren.

Er besagt, dass der chromatische Index eines Graphen entweder dem maximalen Knotengrad oder diesem plus eins entspricht.

Einen Graphen, der ohne Kantenüberschneidungen in der Ebene gezeichnet werden kann.

Ein Graph, in dem mehrfache Kanten zwischen denselben Knoten erlaubt sind.

Die Anzahl der Kanten, die an einen Knoten angrenzen.

In bipartiten Graphen entspricht die Größe eines minimalen Knotenüberdeckungssets der Größe eines maximalen Matchings.

Einen Graphen, der keine Kreise enthält.

Eine Zuweisung von Farben zu den Knoten eines Graphen, sodass keine zwei benachbarten Knoten die gleiche Farbe haben.

Eine Folge von Kanten, bei der aufeinanderfolgende Kanten jeweils einen gemeinsamen Knoten teilen.

Eine Menge von Kanten, sodass jeder Knoten des Graphen an mindestens einer dieser Kanten beteiligt ist.

Eine maximale zusammenhängende Teilmenge des Graphen.

Ein Graph, der aus einem planaren Graphen entsteht, indem man für jede Fläche einen Knoten setzt und Kanten zwischen Flächen mit gemeinsamer Kante einfügt.

Ein Algorithmus, der Knoten nacheinander färbt und jedem Knoten die kleinstmögliche verfügbare Farbe zuweist.

Ein Spannbaum eines gewichteten Graphen mit minimaler Gesamtkantenlänge.

Eine vollständige Zuordnung ist möglich, wenn jede Teilmenge von Kandidaten mindestens so viele passende Optionen hat wie die Größe der Teilmenge.