Title

A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs

Authors

Authors

R. Luo;Y. Zhao

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

J. Graph Theory

Keywords

edge coloring; independence number; critical graphs; CONJECTURE; Mathematics

Abstract

In 1968, Vizing conjectured that if G is a Delta-critical graph with n vertices, then alpha(G)<= n/2, where alpha(G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that alpha(G)<(((5 Delta-6)n)/(8 Delta-6))<5n/8 if Delta >= 6. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202-212, 2011

Journal Title

Journal of Graph Theory

Volume

68

Issue/Number

3

Publication Date

1-1-2011

Document Type

Article

Language

English

First Page

202

Last Page

212

WOS Identifier

WOS:000295965400003

ISSN

0364-9024

Share

COinS