complete bicolored graph | complete bicoloured graph | complete bigraph

A complete bipartite graph, sometimes also called a complete bicolored graph or complete bigraph, is a bipartite graph (i.e., a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent. If there are p and q graph vertices in the two sets, the complete bipartite graph is denoted K_(p, q). The above figures show K_(3, 2) and K_(2, 5). K_(3, 3) is also known as the utility graph (and is the circulant graph Ci_(1, 3)(6)), and is the unique 4-cage graph. K_(4, 4) is a Cayley graph. A complete bipartite graph K_(n, n) is a circulant graph, specifically Ci_(1, 3, ..., 2⌊n/2⌋ + 1)(n), where ⌊x⌋ is the floor function.

bipartite graph | cage graph | cocktail party graph | complete graph | complete k-partite graph | complete tripartite graph | crown graph | k-partite graph | Thomassen graphs | utility graph | Zarankiewicz's conjecture