Graph Imperfection with a Co-Site Constraint.
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 x v positive integers (colors) to each node v such that th...
| Hauptverfasser: | , |
|---|---|
| Format: | Journal article |
| Sprache: | English |
| Veröffentlicht: |
2004
|
| _version_ | 1826301519788507136 |
|---|---|
| author | Gerke, S McDiarmid, C |
| author_facet | Gerke, S McDiarmid, C |
| author_sort | Gerke, S |
| collection | OXFORD |
| description | 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 x v 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. |
| first_indexed | 2024-03-07T05:33:40Z |
| format | Journal article |
| id | oxford-uuid:e322f1a2-9291-4ee5-9ef4-553da48b7a20 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:33:40Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | oxford-uuid:e322f1a2-9291-4ee5-9ef4-553da48b7a202022-03-27T10:06:45ZGraph Imperfection with a Co-Site Constraint.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e322f1a2-9291-4ee5-9ef4-553da48b7a20EnglishSymplectic Elements at Oxford2004Gerke, SMcDiarmid, CWe 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 x v 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. |
| spellingShingle | Gerke, S McDiarmid, C Graph Imperfection with a Co-Site Constraint. |
| title | Graph Imperfection with a Co-Site Constraint. |
| title_full | Graph Imperfection with a Co-Site Constraint. |
| title_fullStr | Graph Imperfection with a Co-Site Constraint. |
| title_full_unstemmed | Graph Imperfection with a Co-Site Constraint. |
| title_short | Graph Imperfection with a Co-Site Constraint. |
| title_sort | graph imperfection with a co site constraint |
| work_keys_str_mv | AT gerkes graphimperfectionwithacositeconstraint AT mcdiarmidc graphimperfectionwithacositeconstraint |