Title

A New Upper Bound For The Independence Number Of Edge Chromatic Critical Graphs

Keywords

critical graphs; edge coloring; independence number

Abstract

In 1968, Vizing conjectured that if G is a Δ-critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that α(G)<(((5Δ-6)n)/(8Δ-6))/(8Δ-6) )<5n/8 if Δ≥6. Copyright © 2010 John Wiley & Sons, Ltd.

Publication Date

1-1-2011

Publication Title

Journal of Graph Theory

Volume

68

Issue

3

Number of Pages

202-212

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/jgt.20552

Socpus ID

80053296164 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/80053296164

This document is currently not available here.

Share

COinS