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.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.
Find a path-decomposition of pathwidth two for a graph that forms a six-vertex cycle.
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.
For 266 students, based on the graduate reading: Figure 2 of the reading shows a system of intervals used to define both an interval graph and an interval containment graph that have high flip-width.
For the system of intervals in the figure, how many edges belong to the interval containment graph but do not belong to the interval graph? You may assume that all intervals include their endpoints and that when two intervals have endpoints that look vertically aligned, they really are the same endpoints.
How many edges belong to the interval graph but do not belong to the interval containment graph?
Why are these changed edges unimportant for the proof that these graphs have high flip-width?