[091212] TJUOJ 1077 - Channel Allocation

Post date: Sep 13, 2012 5:46:27 AM

http://acm.tju.edu.cn/toj/showp1077.html

As a follow up to our discussions today, I have an example where the BFS method - where you assign colors to vertices greedily following a BFS order - fails.

6

A:BC

B:AF

C:ADE

D:CEF

E:CDF

F:BDE

Here is a graphical representation of it:

If we start by assigning the value 1 to A, then you will end up with this assignment.

However, the optimal coloring is:

Re: Paul, doing this in order of degree wouldn't help at all, because we can make any vertex have an arbitrary degree.