Square-free graphs with no induced fork (Q831350)

Summary: 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 \bigg\lceil\frac{3\omega(G)}{2}\bigg\rceil\) via these structure theorems with some additional work on coloring basic classes.