Claw and co-claw free graphs

An easy to understand subclass of these are the $\{K_3,K_{1,3}\}$-free graphs. (These are a subclass because $K_3$ is a subgraph of $\overline{K_{1,3}}$.)

Such graphs can have maximum degree $2$, because if a vertex $v$ has neighbors $w_1,w_2,w_3$, then either they are independent (and form a $K_{1,3}$ together with $v$) or there is an edge $w_i w_j$ (which forms a triangle together with $v$). So we can classify these completely: they are the disjoint unions of islated vertices, paths, and cycles of length at least $4$.

Similarly, the complements of these graphs form a nice subclass, the $\{\overline{K_3},\overline{K_{1,3}}\}$-free graphs, which we now also understand.

I will now show that these are the only cases when the number of vertices is sufficiently large (at least $11$).

In a general $\{K_{1,3},\overline{K_{1,3}}\}$-free graph, the neighborhood $N(v)$ of any vertex $v$ is $\{\overline{K_3},\overline{K_{1,3}}\}$-free, and the co-neighborhood $\overline{N}(v)$ is $\{K_3,K_{1,3}\}$-free. But these cannot both be large. Whenever $w \in N(v)$ has neighbors $x_1,\dots,x_k$ in $\overline{N}(v)$, then $x_1, \dots, x_k$ must form a clique: if $x_ix_j$ is not an edge, then $\{w,x_i,x_j,v\}$ induce a $K_{1,3}$. But $\overline{N}(v)$ is $K_3$-free, so $k \le 2$. and there are at most $2|N(v)|$ edges between $N(v)$ and $\overline{N}(v)$.

Similarly, there are at most $2|\overline{N}(v)|$ non-edges. But there are $|N(v)| \cdot |\overline{N}(v)|$ pairs of vertices here which are either edges or non-edges. So $$|N(v)| \cdot |\overline{N}(v)| \le 2|N(v)| + 2|\overline{N}(v)| \iff (|N(v)|-2)(|\overline{N}(v)|-2) \le 4.$$

Suppose the graph is large (it has $n>10$ vertices). Then the only way to satisfy this inequality is to make sure that every vertex has either degree or co-degree $2$. But if there's a vertex $v$ with degree at most $2$, and a vertex $w$ with co-degree at most $2$, then there are $n-5$ vertices adjacent to $w$ but not $v$, and among these vertices there cannot be either a $K_3$ or an $\overline{K_3}$. This is impossible by Ramsey's theorem.

Thus, aside from small examples, these graphs either have maximum degree $2$ or maximum co-degree $2$, and we've already figured out what both of these cases are like.

The largest example I've found not of this type is the Paley graph on $9$ vertices,

P(9)

which you can find on House of Graphs here. (Like all Paley graphs, it's self-complementary, so it's enough to check that it's claw-free, which it is.) I don't have a proof that there is no $10$-vertex example.

Tags:

Graph Theory