Edge colouring

Definition

Let $G$ be a graph with edge set $E$ , and let $C$ be a set of colours. An edge colouring of $G$ is a function $c : E \to C$ such that $c(e) \neq c(e')$ for any two distinct edges $e$ and $e'$ with a common end. The chromatic index $\chi'(G)$ is the smallest number of colours in an edge colouring of a finite graph $G$ .

Remarks

Each colour class is a matching. Thus an edge colouring is a partition of the edges into matchings. The edges at a vertex need different colours, so $\chi'(G) \ge \Delta(G)$ . Vizing's theorem of 1964 says that a simple graph has $\chi'(G) = \Delta(G)$ or $\chi'(G) = \Delta(G) + 1$ .

Where this leads

1 page builds on this one.

Vizing's theorem

Tag	`02CDYWSWSY`
URI	`m2://02CDYWSWSY`
Kind	definition
Writing	W1 stated
MSC	05C15
Defines	Edge colouring

Edge colouring

Definition

Remarks

Where this leads

Further reading

What this page needs for W2

What links here

Results about this

Used by