+1 vote
520 views

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

can somebody explain how ?

| 520 views

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

by Boss (35.5k points)
selected by
0
Can you prove this theorem?
Take any graph find Max degree vertices

Apply the above formula
by Active (1.2k points)
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 (369 points)
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)
by (47 points)

1
+1 vote
2