...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Graph Imperfection
【24h】

Graph Imperfection

机译：图缺陷

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We are interested in colouring a graph G = (V, E) together with an integral weight or demand vector x = (x_v: v ∈ V) in such a way that x_v colours are assigned to each node v, adjacent nodes are coloured with disjoint sets of colours, and we use as few colours as possible. Such problems arise in the design of cellular communication systems, when radio channels must be assigned to transmitters to satisfy demand and avoid interference. We are particularly interested in the ratio of chromatic number to clique number when some weights are large. We introduce a relevant new graph invariant, the "imperfection ratio" imp(G) of a graph G, present alternative equivalent descriptions, and show some basic properties. For example, imp(G) = 1 if and only if G is perfect, imp(G) = imp(G-bar) where G-bar denotes the complement of G, and imp(G) = g/(g-1) for any line graph G where g is the minimum length of an odd hole (assuming there is an odd hole).
机译：我们有兴趣对图形G =（V，E）以及整数权重或需求向量x =（x_v：v∈V）进行着色，以使x_v颜色分配给每个节点v，相邻节点被着色不相交的颜色集，而我们使用的颜色则越少越好。当必须将无线信道分配给发射机以满足需求并避免干扰时，在蜂窝通信系统的设计中会出现这样的问题。当某些权重较大时，我们对色数与团数之比特别感兴趣。我们引入了一个相关的新图不变式，即图G的“​​不完美率” imp（G），给出了等效的替代描述，并显示了一些基本属性。例如，当且仅当G为完美时，imp（G）= 1，imp（G）= imp（G-bar）其中G-bar表示G的补数，并且imp（G）= g /（g-1 ）对于任何线图G，其中g是奇数孔的最小长度（假设有一个奇数孔）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号