Find the smallest value of k such that the following graphs

Find the smallest value of k such that the following graphs are k - partite: C3, C5, C7, C9 , C11 ( These are the Cycle Graphs)

Solution

For a partite graph k- partite it should be partitioned into k independent sets such that the edges linking should belong to different set and not to same set

For C3 the only possibility (1,1,1)

For C5 the possibilities are (1,2,2) or (2,1,2) or (2,2,1)

For C7 the possibilities are (2,2,3) or (2,3,2) or (3,2,2)

For C9 the possibilities are (4,3,2) or (4,2,3) or (2,3,4) or (2,4,3) or (3,2,4) or (3,4,2)

For C11 the possibilities are various possibilies one of them being (5,3,3) and its permutatations (3,3,5) ,(3,5,3)

so the smalllest value of k=3