Traceability Of Graph And Discussion Of Coloring Property Of Product Of Graphs

In the first part of this paper , based on the degree sum of independent set with three vertex , discussed the traceability of n ?extendable graph . About n ?extendable graph , in 1957,Berge put forward the n ?extendable path first in reference [2].However some scholar studied the degree sum , traceability and Hamilton property of n ?extendable graph ,since Plumer draw into the conception of n ?extendable graph in 1980 ,in reference [3]and got series of result [ 3? 5].In 2001 , Ken-ichi Kawarabayashi , Katsuhiro Ota and Akira Saito revealed the relation between degree sum and Hamilton property of n ?extendable graph in reference [4] and relation between n ?extendable graph and complete graphs furthermore .In 1996 professor A Yongga based on degree sum of graph that degree more than 3 ,got a sufficient condition of traceable in reference [5] .In this paper , based on studies of above we discuss the traceable property of n ?extendable graph by degree sum .In second part , mainly discussed the abundant condition of the equivalent proposition of Hedeteniemi's conjecture .Coloring problem is a focus of the public in graph theory . Coloring problem originated from a very famous conjecture——four color conjecture[6]. People capture thi-s conjecture in different ways since it is put forward by Guthre.F in 1852 , but there haven't strict analytic proof of it . Hedeteniemi.S revealed relation between color of two graphs and their product by a con-jecture in reference [7],called Hedeteniemi's conjecture . Hedeteniem-i's conjecture studies coloring problem in algebraic way. There have n-o proof of Hedeteniemi's conjecture for graphs that degree more than 5. Benoit Larose, Claude Tardif studied the Hedetniemi's conjecture in vi-ew of retract and proved that the conjecture is hold for vertex transi-tive core graph ,if it is projective .In this paper , we proved equivalence proposition of Hedetniemi's conjecture is true for some special graphs based on the above results of study and abundant condition of a graph to be core .