Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 17 Edge-Colouring
Tags: fromAlgorithm hasNotNewEffectReturnsMeaning oldAlgoNewName

Name: A \(k\)-edge colouring
Definition: A mapping \(c:E\to S\) with \(S\) a set of \(k\) colours
Page: 451
Chapter: 17
Section: 1
Variables: \(G\) a graph
\(k\in\mathbb N\)
Definition2: A \(k\)-partition of \(E\)

Name: A colour classe
Definition: A maximal set of edges having the same colours
Page: 451
Chapter: 17
Section: 1
Variables: \(G\) a graph
\(c\) an edge colouring

Name: A \(k\)-edge-colourable graph
Definition: A graph admitting a proper \(k\)-edge-colouring
Page: 451
Chapter: 17
Section: 1
Variables: \(k\in\mathbb N\)

Smaller0: \(G\) is \(k\)-colourable
Greater0: \(G\) is loopless
Page: 451
Chapter: 17
Section: 1
Variables: \(G\) a graph,
\(k\in\mathbb N\)

Name: The edge chromatic number of \(G\)
Definition: The least \(k\) such that \(G\) is \(k\)-edge-colourable
Page: 452
Chapter: 17
Section: 1
Variables: \(G\) a graph,
Notation: \(\xi'(G)\)
Example: 0
Applied to: empty graph

Name: A \(k\)-edge chromatic graph
Definition: A graph whose edge chromatic value is \(k\)
Page: 452
Chapter: 16
Section: 1
Variables: \(k\in\mathbb N\)
Kind: Prop

Page: 452
Implementation: Find edge-chromatic value of the graph, with an edges for each \(p_{ij}\) between \(x_i\) and \(y_j\)
Section: 1
Chapter: 16
Variables: In a school:
there are \(m\) teachers, and
\(n\) classes.
Given that teacher \(x_i\) is required to teach class \(y_j\) for \(p_{ij}\) periods
Name: The Timetabling Problem
Returns: schedule a complete timetable in the minimum number of periods
Kind: Ex