Files in this item
Files  Description  Format 

application/pdf Gregory_Puleo.pdf (589kB)  (no description provided) 
Description
Title:  Problems in list coloring, triangle covering, and pursuitevasion 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 UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Tuza's conjecture
packing and covering list coloring pursuitevasion 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 edgedisjoint triangles, then G can be made trianglefree 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 trianglefree, 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 GX 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 ErdosGallaiTuza~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) <= 5V(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 btuple 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 non2choosable graph is (4:2)choosable. We disprove Voigt's conjecture, characterize which minimial non2choosable graphs are (4:2)choosable, and conjecture an extension of Rubin's characterization of the 2choosable graphs. Finally, in Chapter 5 we study the game of Revolutionaries and Spies, a pursuitevasion 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:  20140916 
URI:  http://hdl.handle.net/2142/50548 
Rights Information:  Copyright 2014 by Gregory J. Puleo 
Date Available in IDEALS:  20140916 
Date Deposited:  201408 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois