一个着色问题。

输入：顶点集V（G），并且顶点的拓扑为格形Grid，但边不确定；给定K种颜色；
输出：着色图，边集E（G），及其与K的关系。
约束条件：（1）任意顶点度d(v)<=2;
  （2）相信边着色不同；
  （3）给新边着色时，其颜色应是两跳范围内使用最少的颜色。

附注：这是一个从通信网中多信道分配中产生的问题，即：信道分配的准则选择两跳范围内使用节点数最少的信道。具体如下：
  每个节点有两个无线接口，每个接口都可动态切换信道，可用信道数为K（K可变，因为不同的网卡支持不同的标准，如ieee802.11a可支持12个信道，而b则有3个信道）。节点格形分布，即：地理上均匀分布，节点间距离为R（节点的通信范围亦为250米，干扰范围为550米）。问题是，依以上分配准则，最终各信道的使用节点数应该基本相等，但如何从数学上证明并求出最终的表达式？尤其是节点密度与信道数之间的关系？ 似乎这不是一个标准的着色问题，因为边集没确定，而且边及边的颜色是动态生成的，所以不知道该如何确定，因此拿出来大家一起讨论，更希望得到高手的提点，谢谢！