Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp017m01bp534
 Title: Bounding Chromatic Numbers for Two Classes of Fork-Free Graphs Authors: Kaufmann, Jenny Advisors: Chudnovsky, Maria Department: Mathematics Class Year: 2019 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$$. URI: http://arks.princeton.edu/ark:/88435/dsp017m01bp534 Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2020