Gallai–Hasse–Roy–Vitaver Theorem
   HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the
orientations ''Orientations'' is a bimonthly print magazine published in Hong Kong and distributed worldwide since 1969. History ''Orientations'' was launched in 1969 by Adrian Zecha (who was later the founder of Aman Resorts) to showcase Asian art and cu ...
of its edges. It states that the minimum number of colors needed to properly color any graph G equals one plus the length of a
longest path In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path may ...
in an
orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building des ...
of G chosen to minimize this path's The orientations for which the longest path has minimum length always include at least one This theorem implies that every orientation of a graph with contains a simple directed path with this path can be constrained to begin at any vertex that can reach all other vertices of the oriented


Examples

A
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
may be oriented from one side of the bipartition to the other. The longest path in this orientation has length one, with only two vertices. Conversely, if a graph is oriented without any three-vertex paths, then every vertex must either be a source (with no incoming edges) or a sink (with no outgoing edges) and the partition of the vertices into sources and sinks shows that it is In any orientation of a
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
of odd length, it is not possible for the edges to alternate in orientation all around the cycle, so some two consecutive edges must form a path with three vertices. Correspondingly, the chromatic number of an odd cycle is three.


Proof

To prove that the chromatic number is greater than or equal to the minimum number of vertices in a longest path, suppose that a given graph has a coloring with k colors, for some number k. Then it may be acyclically oriented by numbering colors and by directing each edge from its lower-numbered endpoint to the higher-numbered endpoint. With this orientation, the numbers are strictly increasing along each directed path, so each path can include at most one vertex of each color, for a total of at most k vertices per To prove that the chromatic number is less than or equal to the minimum number of vertices in a longest path, suppose that a given graph has an orientation with at most k vertices per simple directed path, for some Then the vertices of the graph may be colored with k colors by choosing a maximal acyclic subgraph of the orientation, and then coloring each vertex by the length of the longest path in the chosen subgraph that ends at that vertex. Each edge within the subgraph is oriented from a vertex with a lower number to a vertex with a higher number, and is therefore properly colored. For each edge that is not in the subgraph, there must exist a directed path within the subgraph connecting the same two vertices in the opposite direction, for otherwise the edge could have been included in the chosen subgraph; therefore, the edge is oriented from a higher number to a lower number and is again properly The proof of this theorem was used as a test case for a formalization of
mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
by


Category-theoretic interpretation

The theorem also has a natural interpretation in the
category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...
of directed graphs and
graph homomorphism In the mathematics, mathematical field of graph theory, a graph homomorphism is a mapping between two graph (discrete mathematics), graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs tha ...
s. A homomorphism is a map from the vertices of one graph to the vertices of another that always maps edges to edges. Thus, a of an undirected may be described by a homomorphism from G to the If the complete graph is given an orientation, it becomes a
tournament A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...
, and the orientation can be lifted back across the homomorphism to give an orientation In particular, the coloring given by the length of the longest incoming path corresponds in this way to a homomorphism to a transitive tournament (an acyclically oriented complete graph), and every coloring can be described by a homomorphism to a transitive tournament in this Considering homomorphisms in the other direction, instead of a directed has at most k vertices in its longest path if and only if there is no homomorphism from the
path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
P_ Thus, the Gallai–Hasse–Roy–Vitaver theorem can be equivalently stated as follows:
For every directed there is a homomorphism from G to the transitive tournament if and only if there is no homomorphism from the path
In the case that G is acyclic, this can also be seen as a form of
Mirsky's theorem In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for and is closely ...
that the longest chain in a
partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
equals the minimum number of antichains into which the set may be This statement can be generalized from paths to other directed graphs: for every there is a dual directed such that, for every directed there is a homomorphism if and only if there is not a homomorphism to


History and related results

The Gallai–Hasse–Roy–Vitaver theorem has been repeatedly It is named after separate publications by and Roy credits the statement of the theorem to a conjecture in a 1958 graph theory textbook by It is a generalization of a much older theorem of László Rédei from 1934, that every
tournament A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concen ...
(an oriented complete graph) contains a directed
Hamiltonian path In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vert ...
. Rédei's theorem follows immediately from the Gallai–Hasse–Roy–Vitaver theorem applied to an undirected complete graph. Instead of orienting a graph to minimize the length of its longest path, it is also natural to maximize the length of the shortest path, for a
strong orientation In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an Orientation (graph theory), orientation) that makes it into a strongly connected graph. Strong orientations have been applied to the des ...
(one in which every pair of vertices has a shortest path). Having a strong orientation requires that the given undirected graph be a bridgeless graph. For these graphs, it is always possible to find a strong orientation in which, for some pair of vertices, the shortest path length equals the length of the
longest path In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path may ...
in the given undirected


References

{{DEFAULTSORT:Gallai-Hasse-Roy-Vitaver theorem Graph coloring Theorems in graph theory Duality theories