CompSci 163/265, Spring 2015, Homework 9

  1. Recall that a chordal graph is a graph in which there is a perfect elimination ordering (an ordering of the vertices such that, for each vertex $v$, the neighbors of $v$ that are earlier in the ordering form a clique). Give pseudocode for finding a maximum clique in a chordal graph. You may assume that a perfect elimination ordering of the graph has already been constructed. (Hint: look for the vertex in the clique that comes last in the ordering.)

  2. Let $G$ be a graph shown below. Prove that $G$ is not an interval graph. That is, show that it is not possible to find a set of six intervals in a line whose intersection pattern is this graph.

  3. For each of the five Platonic solids (the tetrahedron, cube, octahedron, icosahedron, and dodecahedron) determine whether the corresponding graph is a perfect graph. For each graph that is not perfect, describe how to find an induced subgraph that is either an odd cycle of length greater than four, or the complement of an odd cycle of length greater than four. For each graph that is perfect, explain why.

    (You may find the following facts helpful: every bipartite graph is perfect, every complete graph is perfect, and the complement of a cycle of length exactly five is another cycle of length five.)

  4. 163 only:

    Find an example of a tree, and a degeneracy ordering on your tree, such that using the greedy coloring algorithm with this ordering colors the tree with more than the optimal number of colors.

    263 only:

    Suppose that $T$ is a tree with a degeneracy ordering $\sigma$ such that using the greedy coloring algorithm with this ordering colors $T$ with $c$ colors. Show how to modify $T$ and $\sigma$ to produce a tree $T'$ with a degeneracy ordering $\sigma'$ such that using the greedy coloring algorithm with this ordering colors $T'$ with $c+1$ colors.