Erdos-Posa theorems for undirected group-labelled graphs

Erdős and Pósa proved in 1965 that cycles satisfy an approximate packing-covering duality. Finding analogous approximate dualities for other families of graphs has since become a highly active area of research due in part to its algorithmic applications. In this thesis we investigate the Erdős-Pósa property of various families of constrained cycles and paths by developing new structural tools for undirected group-labelled graphs. Our first result is a refinement of the flat wall theorem of Robertson and Seymour to undirected group-labelled graphs. This structure theorem is then used to prove the Erdős-Pósa property of A-paths of length 0 modulo p for a fixed odd prime p, answering a question of Bruhn and Ulmer. Further, we obtain a characterization of the abelian groups Γ and elements l ∈ Γ for which A-paths of weight l satisfy the Erdős-Pósa property. These results are from joint work with Robin Thomas. We extend our structural tools to graphs labelled by multiple abelian groups and consider the Erdős-Pósa property of cycles whose weights avoid a fixed finite subset in each group. We find three types of topological obstructions and show that they are the only obstructions to the Erdős-Pósa property of such cycles. This is a far-reaching generalization of a theorem of Reed that Escher walls are the only obstructions to the Erdős-Pósa property of odd cycles. Consequently, we obtain a characterization of the sets of allowable weights in this setting for which the Erdős-Pósa property holds for such cycles, unifying a large number of results in this area into a general framework. As a special case, we characterize the integer pairs (l, z) for which cycles of length l mod z satisfy the Erdős-Pósa property. This resolves a question of Dejter and Neumann-Lara from 1987. Further, our description of the obstructions allows us to obtain an analogous characterization of the Erdős-Pósa property of cycles in graphs embeddable on a fixed compact orientable surface. This is joint work with Pascal Gollin, Kevin Hendrey, O-joung Kwon, and Sang-il Oum.

Level thesis:degree_level

Doctoral

Department dc:contributor.department

Mathematics

Grantor dc:publisher

Georgia Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Yoo, Youngho

Advisor dc:contributor.advisor

• Yu, Xingxing

Committee members dc:contributor.committeemember

• Bernshteyn, Anton
• Blekherman, Grigoriy
• Liu, Chun-Hung
• Singh, Mohit

• Graph theory, combinatorics

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/1853/67225

OAI identifier oai:identifier

oai:repository.gatech.edu:1853/67225