Dissertation Defense Announcement

The College of Arts and Sciences announces the Final Dissertation of

Kamil Popielarz

for the Degree of Doctor of Philosophy

on March 26, 2018 at 2:00 PM in Room 245, Dunn Hall

Advisor: Béla Bollobás

Problems in Extremal Graph Theory

ABSTRACT: This dissertation concerns several results in extremal graph theory. 1. A solution to an asymptotic version of conjectures of Caro and Yuster, and Caro, Lauri, and Zarb concerning the existence of large induced subgraphs with many vertices of same, almost maximum degree. 2. A graph is said to be path-pairable if for any pairing of its vertices there exist edge disjoint paths joining the vertices in each pair. The notion of path-pairable graphs was introduced by Csaba, Faudree, Gyárfás, Lehel, and Schelp in 1992. Here we prove several results about the extremal behavior of maximum degree and diameter in some class of path-pairable graphs. In particular, we show that every path-pairable planar graph has a vertex of linear degree. 3. Improving recent results of Ferrara, Jacobson, Pfender and Wenger, and generalizing a recent result of Roberts we provide bounds, which are tight up to a multiplicative constant, on the partite-saturation numbers of complete graphs. Along the way, we disprove a conjecture and answer a question of Ferrara et al. 4. A majority coloring of a digraph is a coloring of its vertices in such a way that no vertex receives the same color as more than half of its outneighbors. Here we solve a number of problems concerning the majority coloring recently studied by Kreuzter, Oum, Seymour, van der Zypen, and Wood. Moreover, we prove similar results for a more general concept called majority choosability. 5. The graph burning number of a graph is a graph parameter introduced by Bonato, Janssen, and Roshanbin to measure the speed of the spread of contagion in a graph. We prove tight bounds on the graph burning numbers in several classes of graphs, and make a progress towards a conjecture of Bonato et al. about the upper bound of the burning number of a connected graph.