Please use this identifier to cite or link to this item:

`http://arks.princeton.edu/ark:/88435/dsp01tb09j840d`

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. |

URI: | http://arks.princeton.edu/ark:/88435/dsp01tb09j840d |

Type of Material: | Princeton University Senior Theses |

Language: | en |

Appears in Collections: | Mathematics, 1934-2020 |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

KALEMAJ-IDEN-THESIS.pdf | 773.31 kB | Adobe PDF | Request a copy |

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