首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Achieving maximum chromatic index in multigraphs
Authors:JM McDonald
Institution:Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1
Abstract:Let G be a multigraph with maximum degree Δ and maximum edge multiplicity μ. Vizing’s Theorem says that the chromatic index of G is at most Δ+μ. If G is bipartite its chromatic index is well known to be exactly Δ. Otherwise G contains an odd cycle and, by a theorem of Goldberg, its chromatic index is at most View the MathML source, where go denotes odd-girth. Here we prove that a connected G achieves Goldberg’s upper bound if and only if G=μCgo and (go−1)∣2(μ−1). The question of whether or not G achieves Vizing’s upper bound is NP-hard for μ=1, but for μ≥2 we have reason to believe that this may be answerable in polynomial time. We prove that, with the exception of μK3, every connected G with μ≥2 which achieves Vizing’s upper bound must contain a specific dense subgraph on five vertices. Additionally, if Δμ2, we prove that G must contain K5, so G must be nonplanar. These results regarding Vizing’s upper bound extend work by Kierstead, whose proof technique influences us greatly here.
Keywords:Chromatic index  Multigraph  Subgraph  Odd-girth
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号