Bounding Chromatic Numbers for Two Classes of Fork-Free Graphs

Abstract

Given a graph \(G\), let \(\omega(G)\) be its clique number and let \(\chi(G)\) be its chromatic number. The claw is the star graph \(K_{1,3}\), the fork is the tree constructed from a claw by adding a vertex adjacent to a leaf, and the dart is the graph constructed from a claw by adding a vertex nonadjacent to a leaf and adjacent to the other three vertices. The graph \(C_4\) is the cycle on four vertices. A graph is (\(G_1, \dots G_k\))-free if it contains no induced subgraph in \(\{G_1, \dots G_k\}\). In this thesis we present a set of five graph operations that can be used to construct (fork, \(C_4\))-free graphs starting from (claw, \(C_4\))-free graphs. As a corollary, we obtain a linear \(\chi\)-bound for (fork, \(C_4\))-free graphs \(G\), namely \(\chi(G) \leq 2\omega(G)\). We also obtain a quadratic \(\chi\)-bound for (fork, dart)-free graphs \(G\), \(\chi(G) \leq \omega(G)^2\).