Title

An Application Of Vizing And Vizing-Like Adjacency Lemmas To Vizing'S Independence Number Conjecture 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) ≤ frac(n, 2), where α (G) is the independence number of G. In this note, we apply Vizing and Vizing-like adjacency lemmas to this problem and obtain better bounds for Δ ∈ {7, ..., 19}. © 2008 Elsevier B.V. All rights reserved.

Publication Date

5-6-2009

Publication Title

Discrete Mathematics

Volume

309

Issue

9

Number of Pages

2925-2929

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2008.06.019

Socpus ID

67349206158 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS