The Gateway to Computer Science Excellence
+1 vote

chromatic number of a graph <= ( maxdegree of the graph ) + 1 

can somebody explain how ?

in Graph Theory by Loyal | 654 views

4 Answers

+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. 


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

by Boss
selected by
Can you prove this theorem?
0 votes
Take any graph find Max degree vertices

Apply the above formula
by Active
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.
by Junior
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)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,892 answers
118,129 users