Graph imperfection and channel assignment (Q2758339)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Graph imperfection and channel assignment |
scientific article; zbMATH DE number 1679723
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Graph imperfection and channel assignment |
scientific article; zbMATH DE number 1679723 |
Statements
25 March 2002
0 references
colouring
0 references
channel assignment
0 references
perfect graphs
0 references
graph imperfection
0 references
imperfection ratio
0 references
Graph imperfection and channel assignment (English)
0 references
The chapter introduces the notion of graph imperfection and shows that this graph parameter is of interest in mobile communications. Let \(G\) be a graph and let every vertex \(v\) of \(G\) be assigned a nonnegative integer \(x_v\). A graph \(G_x\) is obtained from \(G\) by replacing every vertex \(v\) by a clique on \(x_v\) vertices. The imperfection ratio of \(G\) is NEWLINE\[NEWLINEr_k= \max\Biggl\{{\chi(G_x)\over \omega(G_x)}: \omega(G_x)= k\Biggr\}.NEWLINE\]NEWLINE Properties of the imperfection ratio are studied.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].
0 references
