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 |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

KAUFMANN-JENNY-THESIS.pdf | 406.01 kB | Adobe PDF | Request a copy |

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