Independent sets and 2-factors in edge-chromatic-critical graphs

被引：22

作者：

Grünewald, S

Steffen, E

机构：

[1] Uppsala Univ, Linnaeus Ctr Bioinformat, BMC, SE-75124 Uppsala, Sweden

[2] Univ Gesamthsch Paderborn, Int Grad Sch Dynam Intelligent Syst, D-33095 Paderborn, Germany

来源：

JOURNAL OF GRAPH THEORY | 2004年 / 45卷 / 02期

关键词：

chromatic index; edge colorings; critical graphs; independent sets; 2-factors; conjectures of Vizing;

D O I：

10.1002/jgt.10141

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113-118, 2004.

引用

页码：113 / 118

页数：6