List Colorings And Cycle Double Cover Of Graphs

The paper introducing my some researched results on list colorings and cycle double cover conjectures of graphs respectively is divided into two parts. The first part comprises Chapters from one to four. Chapter one is intended as a first introduction to basic concepts and terminations of graphs, together with the background on list coloring of graphs. In Chapter two, we prove that the cartesian product graphs of a cycle and a path satisfy the list edge coloring conjecture. In Chapter three, we study the choosability of a bipartite graph B and obtain (a) Suppose that u∈ B is a odd vertex and that f : V(B) → N is a function such that f(u) = (?) and f(v) =(?) + 1 for v ∈V(B)\u. Then B is f-choosable; (b) Suppose that there are at least d_B(u) — 1 odd vertices in N_b(u) and f : V(B)→N is a function such that f(u) = 1 and f(v) =(?) + 1 for v ∈ V(B)\u. Then B is f-choosable; (c) Suppose that u and w are two nonadjacent vertices in B, where u is an odd vertex and all vertices in N_b(w) are odd, and f :V(B) → N is a function such that f(w) = 1, f(u) = (?) and f(v) =(?) + 1 for v ∈ V{B)\{u,w}. Then B is f-choosable. In Chapter four, we give the choice numbers of some composition graphs of cycle by empty graph.The second part contains only Chapter five. First, we introduce the concept of the color factor by which a sufficient and necessary condition (*) on the existence of the cycle double cover for a cubic graph is obtained. Second, according to the length of circuit and 8-flow theorem, we divide graphs into two classes and by the condition (*) prove that some of them have CDC, respectively.