✦ LIBER ✦

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

✍ Scribed by Stefan Grünewald; Eckhard Steffen

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 66 KB
Volume: 45
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10141

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Edge-chromatic critical graphs and the e

Edge-chromatic critical graphs and the existence of 1-factors

✍ S. A. Choudum 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract We give examples of edge‐chromatic critical graphs __G__ of the following types: (i) of even order and having no 1‐factor, and (ii) of odd order and having a vertex __v__ of minimum degree such that __G__ − __v__ has no 1‐factor. The first disproves a conjecture of S. Fiorini and R. J.

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A

The existence of a 2-factor in K1, n-fre

The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity

✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.