On the size of edge-coloring critical graphs with maximum degree 4

In 1968, Vizing proposed the following conjecture: If G = ( V , E ) is a Δ -critical graph of order n and size m , then m ≥ 1 2 [ ( Δ − 1 ) n + 3 ] . This conjecture has been verified for the cases of Δ ≤ 5 . In this paper, we prove that m ≥ 7 4 n when Δ = 4 . It improves the known bound for Δ = 4 w...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-12, Vol.308 (23), p.5856-5859
Main Authors: Miao, Lianying, Pang, Shiyou
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Conjecture
Edge-coloring
Edge-coloring critical graphs
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 1968, Vizing proposed the following conjecture: If G = ( V , E ) is a Δ -critical graph of order n and size m , then m ≥ 1 2 [ ( Δ − 1 ) n + 3 ] . This conjecture has been verified for the cases of Δ ≤ 5 . In this paper, we prove that m ≥ 7 4 n when Δ = 4 . It improves the known bound for Δ = 4 when n > 6 .
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.10.013