The Colour Numbers of Complete Graphs

An independent set of vertices in an ordinary graph G with vertex set F and edge set X is a subset of V in which no two elements are adjacent, i.e., joined by an edge. The minimum number of independent sets (also called colour classes) into which F can be partitioned is called the (vertex) chromatic number of G and is denoted by x($)In a like manner, we define two other " colour numbers " for a graph 6?. An independent set of edges in G is a subset of X in which no two elements are adjacent, i.e., have an end-vertex in common. The minimum number of independent sets (also called edge colour classes) into which X can be partitioned is called the edge chromatic number of G (also chromatic index, see [1]) and is denoted by x'(@)-^ independent set of vertices and edges in G is a subset of VuX having the properties: (i) no two elements of F are adjacent, (ii) no two elements of X are adjacent, (iii) no element of V is incident with an element of X. The minimum number of such independent sets into which V\JX can be partitioned is called the total chromatic number of G and is denoted by x"($)By Kn, the complete graph of order n, we mean the graph where | F | = w (|F| denotes the cardinal number of F) and \X\ = n(n—l)/2, i.e., all distinct vertices of Kn are adjacent. A graph G with vertex set F is called bipartite if F can be partitioned into sets Vx and F2 so that every edge of G joins a vertex of Vx to a vertex of F2. The complete bipartite graph Km> n is the bipartite graph with | V1 | = m, | F21 = n, and | X | = mn, i.e., every vertex of Vx is adjacent to all vertices of F2. Our purpose here is to establish the colour numbers for the complete graphs and the complete biparite graphs. Some of these results are already known, but they shall be listed for completeness.