backtracking for graph with adj list

0
votes

Consider a graph with adjacency list as given below and with 4 vertices and 4 edges.

  1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0

It is a simple rectangular graph.

In m-colorability graph problem we have to colour the graph with no adjacent nodes of the same color.I am reading a book which says that if the degree of the graph is 'd' then graph can be colored in d+1 ways.But the above graph can be colored in 2 ways which is the degree of the graph.How?

1
algorithmgraph-coloring
1. what do you mean by the degree of the graph? As far as I know only vertices have degrees not graphs. (do you mean minimal degree?) 2. you ask about ways of coloring your graph? or minimal numbers of colors needed to color it? - artur grzesiak
moreover what is the book? and what exactly it says? your graph is clearly colorable with just 2 colors. - artur grzesiak

1 Answers

0
votes

If graph is fully connected then the graph is colorable with d+1 color. In this case it is not fully connected so colors can be less than d+1 which is 3 here and as seen it is 2 in this case.

Note: fully connected means all vertices are connected to each other directly by edge.