= Edge coloring
{title2=$c:E(G)\to\{1,\ldots,k\}$}
{wiki}
= Edge colouring
{synonym}
An <edge colouring> assigns a label called a colour to every <edge of a graph>: it is a <function> $c:E(G)\to\{1,\ldots,k\}$. Here this definition allows arbitrary assignments. Two <edges> sharing a <vertex> may receive the same colour. A <proper edge colouring> imposes the additional condition that such <edges> receive different colours. Some textbooks use "<edge colouring>" as shorthand for this proper version; check the convention before applying a theorem.<Line graphs and edge coloring>[Line graphs and edge coloring, slide 1: arbitrary labeling versus proper edge coloring]{ref}
The distinction matters in <Ramsey theory>. In a red-blue <edge colouring> of a <complete graph>, a <triangle in a graph> is monochromatic when its three <edges> have the same colour. These are arbitrary <edge colourings>: forbidding equal colours on <edges> sharing a <vertex> would forbid the very monochromatic <triangles in a graph> being sought. For example, assigning red to every <edge> of $K_3$ is a valid arbitrary <edge colouring>, although it is not a <proper edge colouring>. Colour labels can also stand for time slots: then <proper edge colouring> turns incompatible jobs into separate rounds.
Back to article page
