Square-Free Graphs with no Induced Fork

Abstract

The claw is the graph $K_{1,3}$, and the fork is the graph obtained from the claw $K_{1,3}$ by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, $C_4$)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, $C_4$)-free graphs that uses the class of (claw, $C_4$)-free graphs as a basic class. Finally, we show that every (fork, $C_4$)-free graph $G$ satisfies $\chi(G)\leqslant \lceil\frac{3\omega(G)}{2}\rceil$ via these structure theorems with some additional work on coloring basic classes.