Introduction to edge-coloring problem

The problem of graph edge coloring, studied in this thesis, relies mainly on coloring the edges of a graph in a way that two distinct adjacent edges are assigned different colors. The challenge is to find the minimum number of colors necessary to give a proper edge coloring to a graph. This minimum number of colors is called the "chromatic index" of a graph $G$ and it is denoted by ­$\chi'(G)$ throughout this thesis. The first chapter of this thesis is an introduction to graph theory, by giving the basic but fundamental definitions of graphs, subgraphs, the concept of connectivity of graphs, also the concepts of matchings and factorization of graphs. The second chapter of this thesis talks about our main topic which is graph edge coloring, giving multiple ways to interpret the parameter $\chi'$, illustrating and proving various important theorems related to finding upper and lower bound for $\chi'$, but also an introduction to the classification problem. We end the second chapter by discussing some types of edge coloring (circular edge coloring, list edge coloring and total coloring). The third and the last chapter of this thesis is a study and description of some main results and statement of some important theorems and conjectures that would help the search and development of efficiently realized coloring algorithms, these algorithms when developed are a huge step forward into determining the chromatic index of graphs which is not an easy task.