✦ LIBER ✦

On the Size of Edge Chromatic Critical Graphs

✍ Scribed by Daniel P. Sanders; Yue Zhao

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 85 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2135

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, by applying the discharging method, we prove that if

📜 SIMILAR VOLUMES

The size of edge chromatic critical grap

The size of edge chromatic critical graphs with maximum degree 6

✍ Rong Luo; Lianying Miao; Yue Zhao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject

New lower bounds for the size of edge ch

New lower bounds for the size of edge chromatic critical graphs

✍ Yue Zhao 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Δ. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004

The independence number of an edge-chrom

The independence number of an edge-chromatic critical graph

✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

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.

The average degree of an edge-chromatic

The average degree of an edge-chromatic critical graph II

✍ Douglas R. Woodall 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract A graph __G__ with maximum degree Δ and edge chromatic number $\chi\prime({G}) > \Delta$ is __edge__‐Δ‐__critical__ if $\chi\prime{(G-e)} = \Delta$ for every edge __e__ of __G__. It is proved that the average degree of an edge‐Δ‐critical graph is at least ${2\over 3}{(\Delta+1)}$ if $\D

Independent sets and 2-factors in edge-c

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

✍ Stefan Grünewald; Eckhard Steffen 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 1 views

## 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 cr