1 citations · 3 across the 15 of their papers we have counts for
6 papers · 1 filter
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…
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Sang-il Oum, Marek Sokołowski
We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining on the empty set. For a connectivity function on an…
Half-integral Erdős-Pósa property for non-null - paths
Vera Chekan, Colin Geniet, Meike Hatzel +4
For a group , a -labelled graph is an undirected graph where every orientation of an edge is assigned an element of so that opposite orientations of the same edge are…
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
Graphs of bounded twin-width are quasi-polynomially -bounded
Michał Pilipczuk, Marek Sokołowski
We prove that for every there is a constant such that every graph with twin-width at most and clique number has chromatic number bounded by $2^{γ_t…
Bounds on half graph orders in powers of sparse graphs
Marek Sokołowski
Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb…