3,415 views

4 Answers

Best answer
6 votes
6 votes

First, you should know that the chromatic number of the graph is the minimum number of color required to color a graph so that no two colors are at the adjacent node

Now if you read the above statement carefully, then you will understand that you can not assign the same color to the node which has a direct edge, and if they do not have a direct edge then you can definitely assign them the same color. 

So, if you consider the above two statement very carefully, then you will come up to RHS of what you are asking that for a graph, the maximum color we need is the ( (max degree of the graph) + 1 ).

But don't always need that much of color to color the graph, sometimes we need very very less than that. Check these simple example: 

Here the max degree is 3, hence at max you need (3+1) color, but you can easily color this graph by using 2 color only. 

Check this one, it has max degree 2, hence it may need max 3 color, but you can easily color this by using 2 color. 

Hence

Chromatic Number <= (max degree of graph) + 1 

selected by
0 votes
0 votes
If a graph have maximum degree as d then there must be a vertex v in G such that it has edges to (d-1) other vertices (so that its degree is d). Now, we'll need at-least (d-1) colors to color these (d-1) vertices because they cannot have same color as vertex v. Total number of colors required is d (including vertex v). That is (d-1) + 1 colors where (d-1) is the degree of graph here.

Rest all the remaining vertices can be colored by reusing the colors.
0 votes
0 votes
suppose max degree of a vertex is n so it has direct edge to n vertices ,for proper coloring all these vertex should be colored with diffrent  n coloand 1 color is required for coloring of that vertex ,so chromatic no=n+1 in max degree case,
hence c.n<=1+d(max)

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
2
Pavan Kumar Munnam asked May 12, 2017
377 views
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
3 votes
3 votes
3 answers
3
Vicky rix asked Apr 7, 2017
1,407 views
A graph consists of only one vertex,which is isolated ..Is that graphA) a complete graph ???B) a clique???C) connected graph ???Please explain your answer ...
0 votes
0 votes
1 answer
4