Das (kardinalitäts-)maximale Matching in einem bipartiten Graphen kann in der Zeit gefunden werden.

Wenn ein bipartiter Graph ist und in ein Matching aufweist, das nicht kardinalitätsmaximal ist, dann gibt es in einen augmentierenden Pfad bezüglich .

Es gibt einen effizienten Algorithmus, der für jeden planaren Graphen eine geeignete Einfärbung in 6 Farben findet.

Wenn ein Graph mit maximalem Grad ist, findet ein Greedy-Algorithmus immer die richtige Einfärbung in höchstens Farben.

Es gibt einen Algorithmus in polynomieller Zeit, der eine -Approximation für das metrische Problem des Handlungsreisenden findet.

Für einen vollständigen Graphen mit gerader Anzahl von Knoten und positiven Gewichten , der die Dreiecksungleichung erfüllt, sei die minimale Kosten-perfekte Paarung und die minimale Kosten-Reise des Handlungsreisenden. Dann ist .

Wenn ein zusammenhängender Graph mit einem maximalen Grad von 100 ist, dann hat eine korrekte Einfärbung in 100 Farben, es sei denn, ist ein vollständiger Graph.

Jeder Zyklus hat eine korrekte 2-Farbgebung.

Jeder Graph ohne Dreieck hat eine chromatische Zahl von höchstens 100.

Jeder -reguläre bipartite Graph für hat ein Matching der Größe .