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

DOI Link

http://dx.doi.org/10.1002/jgt.20552

Language

English

First Page

202

Last Page

212

WOS Identifier

WOS:000295965400003

ISSN

0364-9024

Recommended Citation

"A New Upper Bound for the Independence Number of Edge Chromatic Critical Graphs" (2011). Faculty Bibliography 2010s. 1603.
https://stars.library.ucf.edu/facultybib2010/1603