✦ LIBER ✦

The size of edge chromatic critical graphs with maximum degree 6

✍ Scribed by Rong Luo; Lianying Miao; Yue Zhao

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 216 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20351

No coin nor oath required. For personal study only.

✦ Synopsis

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 conjecture has been verified for $\Delta \leq {{5}}$. In this article, by applying the discharging method, we prove the conjecture for $\Delta = {{6}}$. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 149–171, 2009

📜 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

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

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

Total chromatic number of planar graphs

Total chromatic number of planar graphs with maximum degree ten

✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

Acyclic edge coloring of graphs with max

Acyclic edge coloring of graphs with maximum degree 4

✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conj

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