Wednesday, February 3, 2010

Another Post Just To Prove I Still Post

The latest post on Scat strategy has been half-finished for over a week, as I have been working on presentations of old and new research. Also, I'm still trying to find a new trivia night; I may give up soon and just start posting my own stuff. For now, here's a fun definition:

Let Ak be the set {1, 2, ..., k}. A graph G has an optimal t-tone coloring if each vertex can be assigned a t-element subset of Ak in such a way that if vertices u and v are distance d apart (in other words, the shortest path in G connecting these vertices contains d edges), then their subsets have at most d-1 elements in common.

For example, vertices adjacent to each other can have no shared elements in their subsets, while if the distance between two vertices is greater than t, they may be assigned identical subsets.

No comments: