## Files in this item

FilesDescriptionFormat

application/pdf

Gregory_Puleo.pdf (589kB)
(no description provided)PDF

## Description

 Title: Problems in list coloring, triangle covering, and pursuit-evasion games Author(s): Puleo, Gregory Director of Research: West, Douglas B. Doctoral Committee Chair(s): Kostochka, Alexandr V. Doctoral Committee Member(s): West, Douglas B.; Reznick, Bruce A.; Molla, Theodore Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Tuza's conjecture packing and covering list coloring pursuit-evasion games discharging triangle packing triangle covering Abstract: We study several problems in extremal graph theory. Chapter 2 studies Tuza's Conjecture, which states that if a graph G does not contain more than k edge-disjoint triangles, then G can be made triangle-free by deleting at most 2k edges. Our results in Chapter 2 strengthen previous results on the conjecture, proving that the conjecture holds whenever G has no subgraph of average degree at least 7. Chapter 3 also deals with the problem of making a graph triangle-free, but from a different perspective: we consider a conjecture of Erdos, Gallai, and Tuza regarding triangle independent'' sets of edges. Writing tau_1(G) to denote the size of a smallest edge set X such that G-X is triangle free and writing alpha_1(G) to denote the size of a largest edge set A that contains at most one edge from each triangle of G, the Erdos--Gallai--Tuza~Conjecture states that alpha_1(G) + tau_1(G) <= |V(G)|^2/4 for each graph G. We show that alpha_1(G) + tau_1(G) <= 5|V(G)|^2/16; this improves on the trivial upper bound of (|V(G)| choose 2). We also prove a general upper bound on alpha_1(G). In Chapter 4 we study multiple list coloring, which extends classical list coloring by requiring us to assign multiple colors to each vertex from its list. When L is a list assignment on a graph G, a b-tuple coloring of G assigns to each vertex v a set of b colors from L(v) so that adjacent vertices receive disjoint sets of colors. Voigt conjectured that every bipartite minimal non-2-choosable graph is (4:2)-choosable. We disprove Voigt's conjecture, characterize which minimial non-2-choosable graphs are (4:2)-choosable, and conjecture an extension of Rubin's characterization of the 2-choosable graphs. Finally, in Chapter 5 we study the game of Revolutionaries and Spies, a pursuit-evasion game similar to Cops and Robbers. We use a probabilistic argument to analyze this game on hypercubes by relating it to a problem in extremal set theory, and we present winning strategies for the the spies on several classes of graphs. Issue Date: 2014-09-16 URI: http://hdl.handle.net/2142/50548 Rights Information: Copyright 2014 by Gregory J. Puleo Date Available in IDEALS: 2014-09-16 Date Deposited: 2014-08
﻿