11. Edge colouring of graphs, Xe(G) and its relation to A(G). Vizing's theorem (without proof), Shannon's theorem (without proof), Konig's theorem about the edge chromatic number of bipartite graphs.

Proper Edge Coloring (!!!)

A coloring of the edges of a graph is said to be a proper edge coloring if adjacent edges (edges that share a common endpoint) receive different colors. Note: in any proper edge coloring, the edges of one color class form a matching.

Edge Chromatic Number χₑ(G) (!!!)

The edge chromatic number of a loopless graph G, denoted χₑ(G), is the minimum number of colors required to obtain a proper edge coloring of G.

Class 1 and Class 2 Graphs (!!!)

By Vizing's theorem, every simple graph has χₑ(G) equal to either ∆(G) or ∆(G) + 1. Graphs with χₑ(G) = ∆(G) are called Class 1 graphs. Graphs with χₑ(G) = ∆(G) + 1 are called Class 2 graphs. There is no known polynomial time algorithm to determine which class a given graph belongs to.

Relation Between χₑ(G) and ∆(G) (!!!)

For any loopless graph G: ∆(G) ≤ χₑ(G) ≤ 2∆(G) − 1. The lower bound holds because all edges incident on a maximum degree vertex are mutually adjacent and require different colors. The upper bound holds because any edge is adjacent to at most 2∆(G) − 2 other edges. ( ∆(G) ≤ χₑ(G) ≤ 2∆(G) − 1 )

Vizing's Theorem (!!!)

For any simple graph G: χₑ(G) ≤ ∆(G) + 1. Combined with the lower bound, this means the edge chromatic number of any simple graph is either ∆(G) or ∆(G) + 1. ( ∆(G) ≤ χₑ(G) ≤ ∆(G) + 1 )

Shannon's Theorem (!!!)

For any loopless graph G: χₑ(G) ≤ ⌊3/2 · ∆(G)⌋. This bound is tight, as shown by the fat triangle: a graph on 3 vertices with k parallel edges between every pair, giving ∆(G) = 2k and χₑ(G) = 3k = 3/2 · ∆(G). ( χₑ(G) ≤ 3/2 · ∆(G) )

König's Theorem — Edge Chromatic Number of Bipartite Graphs (!!!)

For any loopless (not necessarily simple) bipartite graph G(A, B, E): χₑ(G) = ∆(G). Bipartite graphs are always Class 1. This is proven by induction on ∆(G): a regular bipartite graph always has a perfect matching, which can be removed and recolored inductively. ( χₑ(G) = ∆(G)