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

- Chordless cycles (co-TT graphs are chordal)
*k*-suns (co-TT graphs are, in fact, strongly chordal)- The bad aster
- 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*_{1}, *a*_{2}, and *a*_{3} be our asteroidal triple, and *X*_{1}, *X*_{2}, and *X*_{3} 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_{1}, recall, is the 3-sun). We will begin with graph III_{2}, which is *S*_{3}. 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*. This vertex may or may not be adjacent to any neighbors of_{i}*a*. In fact, adding a pendant vertex to_{i}*a*is the easiest way to prevent_{i}*a*from being a middle vertex, because it is no longer simplicial._{i} - Category B constructions modify the
*a*-heavy path_{i}*X*by adding_{i}*a*-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._{i} - Category C constructions combine the other two constructions, adding a new neighbor to
*a*which is adjacent to the_{i}*a*-heavy vertices on_{i}*X*, and then adding vertices to_{i}*X*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._{i}

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.

## No comments:

Post a Comment