recategorized by
660 views
1 votes
1 votes
Consider a tree with n nodes, where a node can be adjacent to maximum 4 other nodes.Then the minimum number of color needed to color the tree, so that no two adjacent node gets same color?
recategorized by

1 Answer

2 votes
2 votes
2 colours are required as it is tree no cycle so one colour will be for each level 0 then one colour for level 1 then first colour for level 2 and so on...

Related questions

0 votes
0 votes
1 answer
1
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...
4 votes
4 votes
2 answers
2
Balaji Jegan asked Nov 27, 2018
2,486 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...
3 votes
3 votes
1 answer
3
0 votes
0 votes
0 answers
4
dan31 asked Nov 6, 2018
1,197 views
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?