Journal article
Graph Imperfection II.
- Abstract:
- The imperfection ratio is a graph invariant which indicates how good a lower bound the weighted clique number gives on the weighted chromatic number, in the limit as weights get large. Its introduction was motivated by investigations of the radio channel assignment problem, where one has to assign channels to transmitters and the demands for channels at some transmitters are large. In this paper we show that the imperfection ratio behaves multiplicatively under taking the lexicographic product, which permits us to identify its possible values, investigate its extremal behaviour and its behaviour on random graphs, explore three upper bounds, and show that it is NP-hard to determine. © 2001 Academic Press.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 244.4KB, Terms of use)
-
- Publisher copy:
- 10.1006/jctb.2001.2043
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Gerke, S
- Grant:
- 97004215
- Publisher:
- Elsevier
- Journal:
- Journal of Combinatorial Theory, Series B More from this journal
- Volume:
- 83
- Issue:
- 1
- Pages:
- 79-101
- Publication date:
- 2001-01-01
- DOI:
- ISSN:
-
0095-8956
- Language:
-
English
- Keywords:
- Pubs id:
-
102308
- UUID:
-
uuid:cad366ad-dda7-435f-91d6-7b6eacced40c
- Local pid:
-
pubs:102308
- Source identifiers:
-
102308
- Deposit date:
-
2012-12-19
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2001
- Notes:
- Copyright 2001 Academic Press. Published by Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at http://www.elsevier.com/open-access/userlicense/1.0/
- Licence:
- Other
If you are the owner of this record, you can report an update to it here: Report update to this record