Files in this item



application/pdfGregory_Puleo.pdf (589kB)
(no description provided)PDF


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
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Tuza's conjecture
packing and covering
list coloring
pursuit-evasion games
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
Rights Information:Copyright 2014 by Gregory J. Puleo
Date Available in IDEALS:2014-09-16
Date Deposited:2014-08

This item appears in the following Collection(s)

Item Statistics