3-Tree

A 3-tree is the case of a k-tree. It is obtained from the complete graph by repeatedly adding a new graph vertex adjacent to exactly the three vertices of an existing triangle graph. This convention requires at least four vertices. An alternate convention also includes (Gainer-Dewar 2012, pp. 1-2).

A 3-tree on vertices has edges. Under the main convention, it is a chordal graph with treewidth 3 and chromatic number 4. Under the alternate convention, the exceptional case has treewidth 2 and chromatic number 3. In either convention, the chromatic polynomial is

where the formula is immediate for the exceptional ; otherwise, the initial has proper vertex colorings, and each added graph vertex has available colors.

Unlike a 2-tree, a 3-tree need not be a planar graph. For example, adding two vertices to the same triangle graph of gives a six-vertex 3-tree containing the complete bipartite graph as a subgraph.

The planar 3-trees, also called stacked triangulations or Apollonian networks, are obtained by inserting each new graph vertex into a triangular graph face and joining it to the three boundary vertices (Ueckerdt et al. 2022, p. 2). Examples include the tetrahedral graph, tritetrahedral graph, triakis tetrahedral graph, and Goldner-Harary graph.