✦ LIBER ✦

New lower bounds for the size of edge chromatic critical graphs

✍ Scribed by Yue Zhao

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 108 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10173

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

On the Size of Edge Chromatic Critical G

On the Size of Edge Chromatic Critical Graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 85 KB

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

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

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 bounds for the chromatic number of g

New bounds for the chromatic number of graphs

✍ Manouchehr Zaker 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph

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.