• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Chromatic index determined by fractional chromatic index
【24h】

Chromatic index determined by fractional chromatic index

机译：由分数色指数确定的色指数

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

摘要

Given a graph G possibly with multiple edges but no loops, denote by Delta the maximum degree, a the multiplicity, mu the chromatic index and chi' f the fractional chromatic index of chi(f)' the fractional chromatic index of G, respectively. It is known that Delta = (chi f)' = chi'= Delta +mu where the upper bound is a classic result of Vizing. While deciding the exact value of chi' is a classic NP-complete problem, the computing of chi(f)' is in polynomial time. In fact, it is shown that if chi(f)' Delta then chi(f)' = max vertical bar E(H) vertical bar/ left perpendicular vertical bar V(H)/2 vertical bar right perpendicular, where the maximality is taken over all induced subgraphs H of G. Gupta (1967), Goldberg (1973), Andersen (1977), and Seymour (1979) conjectured that chi' = [chi(f)'] if chi' = Delta + 2, which is commonly referred as Goldberg's conjecture. It has been shown that Goldberg's conjecture is equivalent to the following conjecture of Jakobsen: For any positive integer m with m = 3, every graph G with chi' m/m-1 Delta + m-3/m-1 satisfies chi' = [chi(f)']. Jakobsen's conjecture has been verified for m up to 15 by various researchers in the last four decades. We use an extended form of a Tashkinov tree to show that it is true for m = 23. With the same technique, we show that if chi' = Delta + 3 root Delta/2 then chi' = [chi(f)']. The previous best known result is for graphs with chi' Delta + root Delta/2 obtained by Scheide, and by Chen, Yu and Zang, independently.Moreover, we show that Goldberg's conjecture holds for graphs G with Delta = 23 or vertical bar V(G) vertical bar = 23. (C) 2018 Elsevier Inc. All rights reserved.
机译：给定可能具有多个边缘但没有环的图G，表示通过Delta最大程度，多重，μ彩色指数和Chi（f）'分别的小数色度指数。众所周知，Δ＆ =（chi f）'＆ = chi'＆ =Δ=Δ+ mu，其中上限是振动的经典结果。虽然决定Chi'的确切值是一个经典的NP完整问题，但Chi（F）'的计算是多项式时间。事实上，它表明，如果chi（f）'＆ Delta然后Chi（F）'= MAX垂直条E（H）垂直杆/左垂直垂直条V（H）/ 2垂直条右垂直，其中最大呈现出全部诱导的G.Gupta（1967）的诱导子图H. ，戈德伯格（1973），安德森（1977），Seymour（1979）劝导Chi'= [Chi（F）']如果Chi'＆ = Delta + 2，这通常被称为Goldberg的猜想。已经表明，Goldberg的猜想相当于jakobsen的猜想：对于任何带有m＆gt的正整数m; = 3，每个图表g与chi'＆ M / M-1Δ+ M-3 / M-1满足Chi'= [Chi（F）']。在过去的四十年中，jakobsen的猜想已经验证了各种研究人员最多15名。我们使用扩展形式的Tashkinov树，以表明M＆ = 23.用相同的技术，我们表明如果chi'＆ = delta + 3根δ/ 2那么chi'= [chi（ F）']。以前的最着名的结果是有关Chi'和GT的图表。 Scheide获得的Delta + Root Delta / 2，由Chen，Yu和Zang，独立地。我们展示了Goldberg的猜想为具有Delta＆ = 23或垂直条V（g）垂直杆的图表G. 。（c）2018 Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号