Skip navigation
Please use this identifier to cite or link to this item:
Title: Feedback Vertex Sets and Cycle Packings in Subcubic Planar Graphs
Authors: Kalemaj, Iden
Advisors: Chudnovsky, Maria
Liu, Chun-Hung
Department: Mathematics
Class Year: 2018
Abstract: For a graph $G$, let $\tau(G)$ denote the minimum size of a set of vertices intersecting every cycle in $G$. Let $\vu(G)$ denote the maximum size of a collection of vertex-disjoint cycles of $G$. Erd\"{o}s and P\'{o}sa~\cite{erdos65} showed that $\tau(G) = O(\vu \log \vu(G))$ for general graphs, and that the bound is tight. Kloks et al.~\cite{kloks} showed that for planar graphs $\tau(G) \leq 5\vu(G)$ and conjectured that $\tau(G) \leq 2\vu(G)$ for any planar graph $G$. The coefficient 5 has been improved to 3 independently in ~\cite{ma, chappell,chen}. However, the conjecture remains open even for subcubic graphs, which are graphs with maximum degree at most 3. We show that for any planar subcubic graph $G$, $\tau(G) \leq \frac{5}{2}\vu(G)$. We also study the connectivity and girth of a vertex-minimal counterexample to the conjecture of Kloks et al. for subcubic graphs. In the end we present a list of reducible configurations, which are graphs $H$, such that if $G$ is a vertex-minimal counterexample to the conjecture of Kloks et al. for planar subcubic graphs, then $G$ cannot contain $H$ as a subgraph.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
KALEMAJ-IDEN-THESIS.pdf773.31 kBAdobe PDF    Request a copy

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