Edge Coloring And Total Coloring Of Some Graphs

A proper k-edge coloring of G is a mapping from E(G) into{1,2, …, k} such that adjacent edges have different colors. The chromatic index χ’(G) of a graph G is the least k such that G has a proper k-edge coloring. A proper k-total coloring of G is a mapping from V(G) ∪ E(G) into{1,2, …, k} such that no incident or adjacent elements (vertices or edges) receive the same colors. The total chromatic number χ"(G) of a graph G is the least k such that G has a proper k-total coloring.In this master thesis, we study the edge coloring and total coloring of some graphs, in-cluding generalized Mycielski graphs, cubic graphs,1-plane graphs, plane graphs and odd graphs. We focus on the Planar Edge Coloring Conjecture, List Edge Coloring Conjec-ture, Total Coloring Conjecture and Unique Maximum Degree Total Coloring Conjecture, and we will give some evidences to support these conjectures.The thesis consists of three chapters.In Chapter 1, we introduce some basic notation, give a chief survey in this direction and state the main results obtained.In Chapter 2, we focus on the edge coloring problem of some graphs and obtain the following results:(1) Characterise the edge chromatic number of generalized Mycielski graphs;(2) Consider the fractional edge chromatic number of planar graphs and show that any cubic graphs are (7,2)-edge colorable;(3) Study the edge coloring and list edge coloring of 1-planar graphs and planar graphs under the condition of the subgraph induced by the maximum degree vertices.In Chapter 3, we focus on the total coloring problem of some graphs.(1) Prove that generalized Mycielski graph satisfies the Total Coloring Conjecture, and also we give some sufficient conditions for a graph to be Type 1;(2) Study the total coloring and list total coloring of 1-planar graphs and planar graphs under the condition of the subgraph induced by the maximum degree vertices;(3) Prove that odd graphs satisfy the Total Coloring Conjecture.