• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Goldberg's conjecture is true for random multigraphs
【24h】

Goldberg's conjecture is true for random multigraphs

机译：Goldberg的猜想对于随机多层来说是如此

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

摘要

In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, the chromatic index x'(G) satisfies X'(G) <= max{Delta(G) [rho(G)]}, where rho(G) = max{e(G[S]/right perpendicular vertical bar S vertical bar/2left perpendicular vertical bar S subset of V}. We show that their conjecture (in a stronger form) is true for random multigraphs. Let M(n, m) be the probability space consisting of all loopless multigraphs with n vertices and m edges, in which in pairs from [n] are chosen independently at random with repetitions. Our result states that, for a given m := m(n), M similar to M(n, m) typically satisfies chi'(G) = max{Delta(G), inverted right perpendicular rho(G)inverted left perpendicular}. In particular, we show that if n is even and in := m(n), then chi'(M) = Delta(M) for a typical M similar to M(n,m). Furthermore, for a fixed epsilon > 0, if n is odd, then a typical M similar to M(n,m) has x/(M) = Delta(M) for m <= (1 - epsilon)n(3) log n, and chi'(M) = inverted right perpendicular rho(G)inverted left perpendicular for m >= (1 + epsilon)n(3) log n. To prove this result, we develop a new structural characterization of multigraphs with chromatic index larger than the maximum degree. (C) 2019 Elsevier Inc. All rights reserved.
机译：在70年代，戈德伯格和独立的Seymour中，介于任何多角形G，色度指数x'（g）满足X'（g）<= max {delta（g）[rho（g）]}，其中rho（ g）= max {e（g n，m）是由n个顶点和m边缘的所有无循环多层物组成的概率空间，其中从[n]成对地选择随机选择，随机选择。我们的结果表明，对于给定的m：= m：= m（n ），与M（n，m）类似的m通常满足Chi'（g）= max {delta（g），反转右垂直rho（g）倒置左侧垂直}。特别是，如果n是偶数并且在：= m（n），然后chi'（m）= delta（m）类似于m（n，m）的典型m。此外，对于固定的epsilon> 0，如果n是奇数，则典型的m类似对于m（n，m）具有x /（m）= delta（m）对于m <=（1 - epsilon）n（3）log n，和chi'（m）=导航rted右垂直rho（g）垂直于m> =（1 + epsilon）n（3）log n。为了证明这一结果，我们开发了具有大于最大程度的色彩指数的多层物的新结构表征。 （c）2019 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号