SELF DOUBT

Question

hows STAR graph bipitrate ???

please help with example . i am doing this by 2 coloring method but not getting any point.

Comments

the main ( hub ) node color by C₁, then remaining all are colored by C₂,  we can color by 2 colors ==> Bi-pertite

---

 

Give one color to the main Node as c1 and c2 to another node. Here Only two color is needed.

Answer 1

In star graph with N nodes has two category of nodes 

one category with degree 1 and the other  category with degree  N-1

First category will contain N-1 nodes ans second category contains one node only

Example,

So we can divide the star graph into two category of nodes and nodes in same category doesn't has an an edge between them.The first category can be colored with single colour and the second category can be coloured with another colour.

                  There for we can call a star graph as bipitrate graph and hence we only need two colors for colouring a star graph.