Due 21/2

1.  Suppose graph G can be embedded into a tree with congestion C,
    dilation D=1 and load L.  Give as good an upper bound on the
    treewidth of G as you can.

2.  Show that on a chordal graph a (weighted) independent set can be
    found in polynomial time.  Hint: look at each step of the analysis
    for the algorithm for general graphs and see if it can be simpler
    for chordal graphs.

3.  Exercise 7 of chapter 10 of Kleinberg Tardos.  Hint for part a: we
    showed in class that a graph of treewidth k must have a vertex of
    degree at most k.  Use this to design a recursive algorithm to
    colour such graph in a small number of colours.

    (This problem will count as 2 problems for grading).

    Exercises 4,5,6 of this chapter are good practice.