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


Independent sets and 2‐factors in edge‐chromatic‐critical graphs
Authors:Stefan Grünewald  Eckhard Steffen
Abstract:In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004
Keywords:chromatic index  edge colorings  critical graphs  independent sets  2‐factors  conjectures of Vizing
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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