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

    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