Graph imperfection and channel assignment

MaRDI QIDQ2758339zbMATH OpenFDO

Authors Colin McDiarmid

Publication date 25 March 2002

zbMATH Keywords

channel assignmentcolouringgraph imperfectionimperfection ratioperfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Applications of graph theory (05C90) Channel models (including quantum) in information and communication theory (94A40)

Review text

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 \[ r_k= \max\Biggl\{{\chi(G_x)\over \omega(G_x)}: \omega(G_x)= k\Biggr\}. \] Properties of the imperfection ratio are studied. For the entire collection see [Zbl 0972.00015].

Recommendations

• Graph imperfection. I
• A graph theoretic approach for channel assignment in cellular networks
• Graph imperfection. II
• Random channel assignment in the plane
• Graph Imperfection with a Co-Site Constraint

Cited in

(7)

• Perfectness and imperfectness of unit disk graphs on triangular lattice points
• Graph imperfection. I
• Graph imperfection. II
• Disproving the normal graph conjecture
• scientific article; zbMATH DE number 15260 (Why is no real title available?)
• Graph Imperfection with a Co-Site Constraint
• Channel graphs of bit permutation networks

This page was built for publication: Graph imperfection and channel assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758339)