Gerke, S and McDiarmid, C (2004) Graph imperfection with a co-site constraint. SIAM Journal on Discrete Mathematics, 17 (3).
Full text access: Open
We are interested in a version of graph coloring where there is a "co-site" constraint value k. Given a graph G with a nonnegative integral demand x(v) at each node v, we must assign xv positive integers (colors) to each node v such that the same integer is never assigned to adjacent nodes, and two distinct integers assigned to a single node differ by at least k. The aim is to minimize the span, that is, the largest integer assigned to a node. This problem is motivated by radio channel assignment where one has to assign frequencies to transmitters so as to avoid interference. We compare the span with a clique-based lower bound when some of the demands are large. We introduce the relevant graph invariant, the k-imperfection ratio, give equivalent definitions, and investigate some of its properties. The k-imperfection ratio is always at least 1: we call a graph k-perfect when it equals 1. Then 1-perfect is the same as perfect, and we see that for many classes of perfect graphs, each graph in the class is k-perfect for all k. These classes include comparability graphs, co-comparability graphs, and line-graphs of bipartite graphs.
This is a Submitted version This version's date is: 2004 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/0aa04fdb-d57d-1029-976c-e5e8bf22d194/5/
Deposited by Research Information System (atira) on 22-Jul-2014 in Royal Holloway Research Online.Last modified on 22-Jul-2014