Study On The Edge Coloring Of Critical Graphs

The study of graph theory started over 200 years ago. The acyclic edge coloring of graphs is an important branch in coloring theory of graphs. And it’s an important research object of graph theory too.If G is a graph of maximum degree D, then the edge chromatic number’c(G) of is either D or D +1. A graph G is said to be of class one if’c(G) = D, and it is said tobe of class two if’c(G) = D +1. A graph G is said to be critical if it is connected,classtwo and’ ’c(G -e) <c(G) for every edge e?E(G). A critical graph G of maxiumum degree is D called a D -critical graph. The Vizing theorem about the edge chromatic number: for any D -critical graph, then’c(G) = D or’c(G) = D +1.By far. This conjecture has been not fully proved. Meanwhile, in 1960, Vizing proposed the Vizing’s independence number conjecture: If G is a D -critical graph, then| |()2VaG ￡. And this conjecture has also been not fully proved. Based on the previous research above, we did a further study on edge chromatic number and independence number in the following 4 chapters.Chapter One introduce the research background, research status and basic definitions.Chapter Two discuss the independence number range about without 2 degree vertices edge coloring critical graph. Using the discharging method proved the following results: when D?{9,10},3 3() | |5 3aG VD -￡D -and D?{11,×××,46}, a(G)15 42| |23 42VD -￡D -.Chapter Three discuss the new lower bound about edge coloring critical graph. We prove the 5-critical graph without 3-cycles edge number lower bouned and 6-critical graph edge number lower bouned, Respectively,12156 m 3n and13352 m 3n Compared to the best results157 m 3n and3313 m 3n, this improves128 n and126n respectively.Chapter Four give some considerable problems for further study.There are totally references in this paper.