Skip navigation
Please use this identifier to cite or link to this item:
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\).
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
KAUFMANN-JENNY-THESIS.pdf406.01 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.