1
$\begingroup$

The problem says:

Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different colors.

Hint : don't think too hard. just color the nodes. what loop invariant do you need?

I was trying to solve this.. but quickly realized a complete graph of 4 vertices, whose vertices have at most 3 neighbors, cannot be colored with one of 3 colors so that each node has different color nodes.

I did some research and it seems like the book had a typo and it should have been "... each node has at most d neighbors, color each node with one of d + 1 colors... "

It is possible to find a graph with maximum degree of d + 1 that can be colored with d + 1 colors but this cannot be true for any graph with max degree of d + 1, right?

Am I correct in assuming that the typo should be corrected like how I did so AND about the last remark?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using $d+1$ colors.

Improve this answer
$\endgroup$
2
  • $\begingroup$ To anyone curious, this is known as Brooks' theorem. $\endgroup$
    – Juho
    Dec 6, 2017 at 20:06
  • $\begingroup$ I made a typo too haha (should've been 'd' instead of 'd+1' neighbors) in my post but you understood it correctly and gave a great answer. thanks! $\endgroup$
    – namesake22
    Dec 7, 2017 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.