Schedulings / Edge Colorings

Question 1

Defn/ An n-edge coloring

Answer 1

assigns colors 1,..n to each edge in G (not necessarily a ‘proper’ covering)

Question 2

Defn/ A proper n-edge coloring is

Answer 2

is an edge coloring s.t. adjacent edges have different colors.

Question 3

Prop: If K is the minimum size of a proper k-edge coloring of G, then Chi(G) = K, where K is the edge chromatic number

Question 4

Prop: Chi(G) >= Del(G)

Question 5

Lemma: If G conn., not an odd cycle, it has a 2-edge coloring, in which both colors are represented at vertices of degree >=2

Answer 5

Eulerian cycle etc. and other BS. Either G eulerian or can be made eulerian

Question 6

Defn/ FOr a k-edge coloring C of graph G, C(v) =

Answer 6

C(v) = # of diff. colored edges incident to v.

Question 7

Defn/ A (not necess. proper) coloring C’ is optimal if

Answer 7

if [allVert]SumC(v) is as large as possible

Question 8

Lemma/ If C is an optimal k-edge coloring and u is a vertex in which color i not represented, and color j is represented twice, G contains an odd cycle

Answer 8

Pf/ Let H be subgraph induced by i and j edges.
If H not an odd cycle, H has 2 coloring with both colors represented at each vert.
This coloring produces a new edge coloring that is better, thus contradict C being optimal.

Question 9

Alg/ Bipartite edge colorings algorithm:

Answer 9

0. Begin with any k coloring.
1. If not proper, then there exists vertex u, where color i is rep. twice, color j not at all.
2. Use lemma to recolor component of induced i,j subgraph. As in, add an imaginary vertex and then,
3. Connect vertices with odd degree to it to make an odd cycle, then recolor based on that.

Question 10

Thm/ (Vizing) (minimum proper edge coloring) Chi’ = Del, or Chi’ = Del + 1.

Answer 10

Wack ass proof