...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On monochromatic component size for improper colourings
【24h】

On monochromatic component size for improper colourings

机译：单色组件尺寸不正确

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

摘要

This paper concerns improper lambda-colourings of graphs and focuses on the sizes of the monochromatic components (i.e., components of the subgraphs induced by the colour classes). Consider the following three simple operations, which should, heuristically, help reduce monochromatic component size: (a) assign to a vertex the colour that is least popular among its neighbours; (b) change the colours of any two adjacent differently coloured vertices, if doing so reduces the number of monochromatic edges-, and (c) change the colour of a vertex, if by so doing you can reduce the size of the largest monochromatic component containing it without increasing the number of monochromatic edges. If a colouring cannot be further improved by these operations, then we regard it as locally optimal. We show that. for such a locally optimal 2-colouring of a graph of maximum degree 4, the maximum monochromatic component size is O(2 ((2log2n)1/2)). The operation set (a)-(c) appears to be one of the simplest that achieves a o(n) bound on monochromatic component size. Recent work by Alon, Ding, Oporowski and Vertigan, and then Haxell, Szabo and Tardos, has shown that some algorithms can do much better, achieving a constant bound on monochromatic component size. However, the simplicity of our operation set, and of the associated local search algorithm, make the algorithm, and our locally optimal colourings, of interest in their own right. (c) 2005 Elsevier B.V. All rights reserved.
机译：本文涉及图的不正确的lambda着色，并着重于单色分量（即由颜色类别引起的子图的分量）的大小。考虑以下三个简单的操作，这些操作应启发性地帮助减小单色分量的大小：（a）为顶点分配在其邻居中最不流行的颜色; （b）更改任何两个相邻的不同着色顶点的颜色，如果这样做会减少单色边的数量，并且（c）更改顶点的颜色，如果这样做可以减小最大单色分量的大小包含它而不增加单色边缘的数量。如果无法通过这些操作进一步改善着色，则我们将其视为局部最佳。我们证明了这一点。对于最大度数为4的图形的这种局部最优2色，最大单色分量大小为O（2（（（2log2n）1/2））。操作集（a）-（c）似乎是实现单色分量大小上的o（n）限制的最简单操作集之一。 Alon，Ding，Oporowski和Vertigan，然后是Haxell，Szabo和Tardos的最新工作表明，某些算法可以做得更好，在单色分量大小上实现恒定的界限。但是，我们的操作集以及相关的局部搜索算法的简单性，使算法和局部最优着色本身就引起了人们的关注。 （c）2005 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号