Document Type
Lecture
Publication Date
10-22-2010
Abstract
A k-edge coloring of a graph G is an assignment of at most k colors to the edges of G in such a way that any two edges meeting at a vertex are assigned different colors. If G has a k-edge coloring, then G is called k-edge colorable. The edge chromatic number, denoted by (G), is the smallest number k for which G is k-edge colorable. A graph G is edge--critical, if (G)= +1 and (G e)= for any edge e of G, where is the maximum degree of G. Vizing conjectured that an edge--critical graph with n vertices has at least ( 1)n+3 2 edges if 3. In this talk, we will introduce some developments and techniques in attempting to prove Vizing's conjecture and present several new results which we obtained recently on bounds of the number of edges in edge--critical graphs.
Relational Format
presentation
Recommended Citation
Li, Xuechao, "Lower Bounds of Edge Critical Graphs" (2010). Combinatorics Seminar. 75.
https://egrove.olemiss.edu/math_combinatorics/75
