Skip navigation
Please use this identifier to cite or link to this item:
Title: Bounded obstructions for three-coloring graphs with lists size two
Authors: Zhang, Emily
Advisors: Chudnovsky, Maria
Contributors: Liu, Chun-Hung
Department: Mathematics
Class Year: 2017
Abstract: Excluding certain subgraphs H from non-3-colorable graphs results in classes of graphs that do or do not have bounded obstructions to coloring. In the positive case, we call those subgraphs H powerful. When the graphs are given a list function L with lists of size 2, we call such H 2-powerful. In this paper we classify all graphs as either 2-powerful or not. In particular, we use propagation paths to show in a simpler way that P\(_{5}\) and P\(_{2}\) + P\(_{3}\) are 2-powerful.
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
thesis6.pdf310.14 kBAdobe PDF    Request a copy

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