CS 163/265, Winter 2025, Practice Problem Set 7

1. Consider a tree that looks like  >-< : it has four leaves, and two degree-three internal nodes. For this tree, find an elimination ordering that cannot be formed by reversing a breadth-first ordering (the order the vertices would be reached by a breadth-first search), regardless of where the search starts or how it orders the neighbors of each vertex.

2. The five platonic solids are listed at https://en.wikipedia.org/wiki/Platonic_solid. Ignoring their faces, you can think of the vertices and edges of them as forming graphs. Three of them form perfect graphs; two do not. State which three are perfect, and for each of these three state whether it is chordal or bipartite. For the two that are not perfect, describe (in terms of the geometry of each shape) how to find an odd hole or the complement of an odd hole.

3. Find a path-decomposition of pathwidth two for a graph that forms a six-vertex cycle.

4. Suppose we are given a path-decomposition of a graph, with pathwidth $w$. Describe a way to use the path-decomposition to order the vertices of the graph so that each vertex has $\le w$ neighbors that are later in the ordering. You should not assume that your graph is an interval graph. Because of this ordering, the graph also has degeneracy $\le w$. Give an example of your ordering for the interval graph used as an example in the "Path decomposition of an interval graph" slide of the lecture notes.