Gallai–Hasse–Roy–Vitaver theorem

ID: gallai-hasse-roy-vitaver-theorem

The Gallai–Hasse–Roy–Vitaver theorem is a result in graph theory that relates two important concepts: the chromatic number of a graph and the length of its longest path, or more specifically, the longest path in its complement. To state the theorem formally, let \( G \) be a connected graph.

New to topics? Read the docs here!