The complete tripartite graph Krst consists of three sets of

The complete tripartite graph Kr,s,t consists of three sets of vertices {a1, . . . , ar} {b1, . . . , bs} {c1, . . . , ct} with edges connecting aibj , aicj , and bicj for all i and j. For which values of r, s, and t is K_{r,s,t} planar?

Solution

Solution :

As noted in Henning Makholm answer, we have the following cases:

a) r 3 , s + t 2

b) r 2 , s + t 4

In both the cases you can show that the graph is planar.

The chromatic number is 3. A complete tripartite graph requires at least

three colors since this graph consists of a bunch of triangles with each vertex of the

triangle in one of the three different sets. It can be done with exactly 3 since the

vertices in the r-vertex set can be one color, in the s-vertex set a second color and the

t-vertex set a third color.