Due Friday, November 11, in Gradescope.
163 students only: For the graph in the "Structure in disease contact graphs" slide of Monday's lecture notes, what is its degeneracy? How many vertices are in the \(k\)-core, for \(k\) equal to the degeneracy? (Hints: If two vertices are shown as overlapping, you may assume that they are adjacent to each other. You can immediately discard everything that is not in the inner circle of vertices, as the initial steps of the all-\(k\)-cores algorithm.)
Both classes: Give an example of an undirected graph \(G\), and a number \(k\), such that the \(k\)-core of \(G\) is not connected.
265 students only: Define the "connected degeneracy" of a graph \(G\) to be the largest number \(k\) such that all \(j\)-cores, for \(j\le k\), are non-empty and connected. Describe the most efficient algorithm you can think of for computing the connected degeneracy. What is its running time? You can analyze your algorithm in terms of \(n\), \(m\), and \(d\) (the numbers of vertices and edges of \(G\), and its degeneracy); you might not need \(d\) in your analysis, but you should not assume that \(d\) is constant.
Suppose that in a graph \(G\), sets of vertices \(X\) and \(Y\) are both maximal cliques with \(x\) and \(y\) vertices in them, respectively. What is the largest possible number of vertices in the intersection \(X\cap Y\)?
If \(C\) is a graph consisting of a single cycle with three, four, or five vertices, then for every vertex ordering the greedy coloring algorithm will find a coloring with the minimum number of colors. Find a vertex ordering for a six-vertex cycle that causes the greedy coloring algorithm to use more than the minimum number of colors. (In describing your answer, you may number the vertices from 1 to 6 around the cycle and then list how these numbers appear in your ordering.)
The greedy coloring algorithm for interval graphs colors the vertices in the left-to-right ordering of the left endpoints of the intervals, giving each vertex the smallest color that is not already used by one of its neighbors. But when all of the intervals have equal lengths (called "unit interval graphs"), there is an even simpler \(k\)-coloring algorithm: use the same order, but color the \(i\)th vertex in the order using the color numbered \(i\) mod \(k\).
163 students only: Find a system of intervals with unequal lengths for which this simpler algorithm does not work: your interval graph is \(k\)-colorable, but coloring it using colors \(i\) mod \(k\) produces an invalid coloring.
265 students only: Explain why, when this simpler algorithm is run on a \(k\)-colorable unit interval graph, each vertex is given a different color than the neighbors that already have colors.