16 citations · 188 across the 122 of their papers we have counts for
28 papers · 1 filter
Fatness and Flatness
Arnold Filtser, Hung Le, Nikolas Mählmann +2
Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of s…
A coarse block-cut tree theorem
Júlia Baligács, Václav Blažej, Jadwiga Czyżewska +2
We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into -connected components. Precisely, we prove that for every graph …
A coarse Menger's Theorem for planar and bounded genus graphs
Václav Blažej, Michał Pilipczuk, Evangelos Protopapas
Menger's Theorem is a fundamental result in graph theory. It states that if in a graph with distinguished sets of terminal vertices and there are no pairwise vertex…
Coarse Balanced Separators in Fat-Minor-Free Graphs
Édouard Bonnet, Hung Le, Marcin Pilipczuk +1
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just b…
Tree decompositions whose trees are subgraphs: An application of Simon's factorization
Romain Bourneuf, Gwenaël Joret, Piotr Micek +2
We show that every connected graph has a tree decomposition indexed by a tree such that is a subgraph of and the width of the tree decomposition is bounded from abo…
Variants of Merge-Width and Applications
Karolina Drabik, Maël Dumas, Colin Geniet +3
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of sev…
Strong odd colorings in graph classes of bounded expansion
Michał Pilipczuk
We prove that for every and a graph class of bounded expansion , there exists some so that every graph from admits a…
Separability Properties of Monadically Dependent Graph Classes
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
On graphs coverable by chubby shortest paths
Meike Hatzel, Michał Pilipczuk
Dumas, Foucaud, Perez, and Todinca [SIAM J. Disc. Math., 2024] proved that if the vertex set of a graph can be covered by shortest paths, then the pathwidth of is bound…
On coarse tree decompositions and coarse balanced separators
Tara Abrishami, Jadwiga Czyżewska, Kacper Kluk +3
It is known that there is a linear dependence between the treewidth of a graph and its balanced separator number: the smallest integer such that for every weighing of the verti…
Obstructions and dualities for matroid depth parameters
Jakub Gajarský, Kristýna Pekárková, Michał Pilipczuk
Contraction-depth is considered to be one of the analogues of graph tree-depth in the matroid setting. In this paper, we investigate structural properties of contraction-de…
Graph classes through the lens of logic
Michał Pilipczuk
Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possi…
Erdős-Pósa property of tripods in directed graphs
Marcin Briański, Meike Hatzel, Karolina Okrasa +1
Let be a directed graphs with distinguished sets of sources and sinks . A tripod in is a subgraph consisting of the union of two --…
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…
Cliquewidth and dimension
Gwenaël Joret, Piotr Micek, Michał Pilipczuk +1
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension as a subposet. This applies in particular to…
Prime and polynomial distances in colourings of the plane
James Davies, Rose McCarty, Michał Pilipczuk
We give two extensions of the recent theorem of the first author that the odd distance graph has unbounded chromatic number. The first is that for any non-constant polynomial w…
Partitioning edges of a planar graph into linear forests and a matching
Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik +1
We show that the edges of any planar graph of maximum degree at most can be partitioned into linear forests and a matching. Combined with known results, this implies that t…
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
The -onion star is the digraph obtained from a star with leaves by replacing every edge by a triple of arcs, where in triples we orient two arcs away from the center, a…
Highly unbreakable graph with a fixed excluded minor are almost rigid
Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk +1
A set in a graph is -unbreakable if every separation of order at most in satisfies or . In this…
Independence number of intersection graphs of axis-parallel segments
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk +1
We prove that for any triangle-free intersection graph of axis-parallel segments in the plane, the independence number of this graph is at least . W…
Transducing paths in graph classes with unbounded shrubdepth
Michał Pilipczuk, Patrice Ossona de Mendez, Sebastian Siebertz
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class ca…
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…
Bounding generalized coloring numbers of planar graphs using coin models
Jesper Nederlof, Michał Pilipczuk, Karol Węgrzycki
We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and orderi…
On objects dual to tree-cut decompositions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is…