Independent sets and 2‐factors in edge‐chromatic‐critical graphs
- 15 December 2003
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 45 (2) , 113-118
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, 2004Keywords
This publication has 3 references indexed in Scilit:
- Chromatic-index-critical graphs of even orderJournal of Graph Theory, 1999
- Chromatic-Index-Critical Graphs of Orders 11 and 12European Journal of Combinatorics, 1998
- SOME UNSOLVED PROBLEMS IN GRAPH THEORYRussian Mathematical Surveys, 1968