8 papers
An Erdős-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
The structure of group-labeled graphs forbidding an immersion
Rose McCarty, Caleb McFarland, Paul Wollan
A -labeled graph is an oriented graph with edges invertibly labeled by a group . We prove a structure theorem for -labeled graphs which forbid a fixed -labeled graph as…
Graphs whose Eulerian trails have unique labels
Donggyu Kim, Rose McCarty, Caleb McFarland
Consider an undirected graph whose edges are labeled invertibly in a group. When does every Eulerian trail from one fixed vertex to another have the same label? We give a precise s…
Almost all graphs are vertex-minor universal
Ruben Ascoli, Bryce Frederickson, Sarah Frederickson +2
Answering a question of Claudet, we prove that the uniformly random graph is -vertex-minor universal with high probability. That is, for some…
Totally -Modular Tree Decompositions of Graphic Matrices for Integer Programming
Caleb McFarland
We introduce the tree-decomposition-based parameter totally -modular treewidth (TDM-treewidth) for matrices with two nonzero entries per row. We show how to solve integer progra…
Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes
Mujin Choi, Maximilian Gorsky, Gunwoo Kim +2
We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd…
Coloring Graphs With No Totally Odd Clique Immersion
Caleb McFarland
We prove that graphs that do not contain a totally odd immersion of are -colorable. In particular, we show that any graph with no totally odd immersion of $K_…
The independence ratio of 4-cycle-free planar graphs
Tom Kelly, Sid Kolichala, Caleb McFarland +1
We prove that every -vertex planar graph with no triangle sharing an edge with a 4-cycle has independence ratio for . This…