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 [email protected]

    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
     

    Accessibility Statement

    This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.