In graph theory, the join operation is a graph operation that combines two graphs by connecting every vertex of one graph to every vertex of the other. The join of two graphs and is denoted , , or .
Let and be two disjoint graphs. The join is a graph with:
In other words, the join contains all vertices and edges from both original graphs, plus new edges connecting every vertex in to every vertex in .
Several well-known graph families can be constructed using the join operation.
The join operation is commutative for unlabeled graphs: .
If has vertices and edges, and has vertices and edges, then has vertices and edges. If and then is connected ( is a subgraph).
The chromatic number of the join satisfies:
This property holds because vertices from and must use different colors (as they are all adjacent to each other), and within each original graph, the minimum coloring is preserved. It was used in a 1974 construction by Thom Sulanke related to the EarthâÂÂMoon problem of coloring graphs of thickness two. Sulanke observed that the join is a thickness-two graph requiring nine colors, still the largest number of colors known to be needed for this problem.
is color critical if and only if and are both color critical.