In Subsection 6.2.1.1, we explored the problem of minimizing the number of colors needed to properly color the vertices of a graph \(G\text{.}\) In the sequel, we consider the problem of coloring edges.
Definition6.2.15.
Let \(G = (V,E)\) be a graph, \(E = \set{e_1, e_2,\ldots, e_n}\text{,}\) and \(C = \set{c_1, c_2, \ldots, c_k}\) a set of labels called colors. A proper edge coloring of \(G\) is a function \(c: E \to C\) such that \(c(e_i) \ne c(e_j)\) if \(e_i \cap e_j \ne \emptyset\text{.}\)
Further, suppose \(C\) admits a proper edge coloring of \(G\text{.}\) We label the cardinality of a smallest such \(C\) the chromatic index of \(G\text{,}\) and use the symbol \(\chi'(G)\text{.}\)
Calculate \(\chi'(C_{2n+1})\text{,}\) where \(n\ge 1\text{.}\) If \(G\) is a graph containing an odd cycle, what can we say about \(\chi'(G)\text{?}\)
Problem6.2.18.
Calculate \(\chi'(K_n)\) for \(3\le n\le 7\text{.}\) Conjecture a value for \(\chi'(K_n)\) for any \(n\ge 3\text{.}\) Can you prove your conjecture?
Problem6.2.19.
Another important class of graphs is that of the complete bipartite graphs. First, calculate \(\chi'(K_{2,2}), \chi'(K_{2,3}), \chi'(K_{3,3}), \chi'(K_{3,4})\text{,}\) and \(\chi'(K_{3,5})\text{.}\) Then, conjecture a value for \(\chi'(K_{m,n})\text{.}\) Can you prove your conjecture?
