Name
Abstract | ||
|---|---|---|
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 xv 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 bipartite graphs and more generally comparability graphs, co-comparability graphs, and line-graphs of bipartite graphs. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1137/S0895480102402514 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
relevant graph invariant,co-comparability graph,bipartite graph,graph g,k-imperfection ratio,graph imperfection,graph k-perfect,comparability graph,adjacent node,co-site constraint,perfect graph,node v | Discrete mathematics,Block graph,Combinatorics,Comparability graph,Line graph,Distance-hereditary graph,Cograph,Pathwidth,Mathematics,Split graph,Graph coloring | Journal |
Volume | Issue | ISSN |
17 | 3 | 0895-4801 |
Citations | PageRank | References |
1 | 0.45 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefanie Gerke | 1 | 199 | 31.63 |
| Colin McDiarmid | 2 | 1071 | 167.05 |