The Gateway to Computer Science Excellence

+1 vote

+5 votes

Best answer

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 **

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.

Rest all the remaining vertices can be colored by reusing the colors.

52,218 questions

59,892 answers

201,086 comments

118,129 users