Lesson 6: There is NO lesson 6

We now know a few of the minimal forbidden subgraphs for the co-TT class of graphs:

1. Chordless cycles (co-TT graphs are chordal)
2. k-suns (co-TT graphs are, in fact, strongly chordal)
3. The bad aster
4. The parasol

Last time, we learned that we can find the minimal strongly asteroidal graphs by modifying the minimal asteroidal graphs to create light paths. Let a₁, a₂, and a₃ be our asteroidal triple, and X₁, X₂, and X₃ the paths connecting them, as described previously.

The only graphs we need concern ourselves with are graphs from the III_n and IV_n families, where n > 1 (graph IV₁, recall, is the 3-sun). We will begin with graph III₂, which is S₃. This graph is unique, because of its rotational symmetry; any of the three asteroidal vertices could be a middle vertex (the rest of the graphs which we have to consider have only one middle vertex, and only one heavy path). This means we must create light paths for each of these vertices. There are several constructions that we can use to prevent an asteroidal vertex a_i from being a middle vertex. I have grouped these constructions into three categories:

• Category A constructions involve adding a vertex adjacent to a_i. This vertex may or may not be adjacent to any neighbors of a_i. In fact, adding a pendant vertex to a_i is the easiest way to prevent a_i from being a middle vertex, because it is no longer simplicial.
• Category B constructions modify the a_i-heavy path X_i by adding a_i-light vertices. When category B constructions are added to more than one of the asteroidal vertices, we also gain the option of adding edges between the newly added vertices. This has to be done carefully; many graphs produced by these constructions are not strongly chordal.
• Category C constructions combine the other two constructions, adding a new neighbor to a_i which is adjacent to the a_i-heavy vertices on X_i, and then adding vertices to X_i which are not (all) adjacent to this new neighbor. These are the most difficult constructions to find, but in at least one case, applying this construction to one asteroidal vertex prevents the entire triple from having a middle vertex.

We'll start with the category A constructions next time. They are fairly simple, so we should be able to get through all of them in one go. This will not be the case for the other two categories.