## DEV Community is a community of 623,065 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Write better code: Day 8 - Graph Coloring

Arjun Rajkumar Updated on ・1 min read

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

--

### Day 8: Question 1

Given an undirected graph with maximum degree DD, find a graph coloring using at most D+1 colors.

-

This problem is from InterviewCake.

## Discussion (1)

Arjun Rajkumar

Logic:

• Each node in the graph has maximum D neighbours.
• Given than there are maximum D+1 colours, we can assume that for each node there is atleast one color that is not used.
• So, go thru each node and get the colors of all its neighbours.
• Check to see which color is not included in this neighbouring color group, and assign the color to it.
``````def colour_graoh(colors, graph)
graph.nodes.each do |node|

all_neighbouring_colors = []

node.neighbours.each do |neighbour|
all_neighbouring_colors << neighbour.color if !all_neighbouring_colors.include?(neighbour.color)
end

colors.each do |color|
node.color = color if !all_neighbouring_colors.include?(color)
break
end
end
``````