# The Structure of Fork-Free $C_4$-Free Graphs

A *claw* is the star graph $K_{1, 3}$. A *fork* is the five-vertex tree with exactly three leaves; i.e. the graph obtained by adding a pendant edge to a claw. A graph is *H-free* if it contains no induced subgraphs isomorphic to $H$. A *hole* is a cycle $C_n$ with $n > 3$. A graph is called *chordal* if it is hole-free. This talk will present a set of four simple operations that can be used to construct fork-free $C_4$-free graphs out of claw-free $C_4$-free subgraphs. In particular, we show that a graph $G$ is fork-free and $C_4$-free if and only if it can be constructed by starting with a claw-free $C_4$-free subgraph $G_0 \subseteq G$ and applying a sequence of these operations. Furthermore, the operations preserve the number of holes in the graph, and hence $G$ is chordal if and only if $G_0$ is chordal.

This is joint work with my adviser, Maria Chudnovsky.