Premium
A new upper bound for the independence number of edge chromatic critical graphs
Author(s) -
Luo Rong,
Zhao Yue
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20552
Subject(s) - independence number , combinatorics , mathematics , chromatic scale , critical graph , graph , upper and lower bounds , adjacency list , discrete mathematics , edge coloring , independence (probability theory) , graph theory , graph power , line graph , statistics , mathematical analysis
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))<5 n /8 if Δ≥6. © 2010 WileyPeriodicals, Inc. J Graph Theory 68: 202‐212, 2011