The graphs studied are assumed to be without loops but may have multiple edges. The “simple” hypothesis thus will mean that the graph is without multiple edges. Given a graph G and an integer k, k-edge-coloring of G is a mapping from the set of the edges of G to a set of k elements called

               Figure 1.1. A k-edge-coloring of a graph (set of colors: {α, β, γ, δ})

colors so that two edges sharing an endpoint are associated in the mapping with different colors.

Given a k-coloring, an edge is said to be of a given color or to have a given color, if in the coloring considered this color is associated with it.

The edge chromatic number of a graph G is the lowest integer k such that a k-coloring of G exists. This integer is denoted by q(G). For example, the chromatic index of the graph shown in Figure1.1 is 4 (check that for this graph there is no edge coloring with less than four colors). The important point of the concept of edge-coloring of a graph is the following property: for each color, the set of the edges having the same color forms what is called a matching, that is a set of edges of the graph such that no two edges share a common endpoint. A k-edge-coloring of a graph G can be seen, more or less a permutation of the colors, as an edge partition of G into matchings. The chromatic index is then the lowest number of classes of such a partition.

This point of view will become useful later.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(65)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength