2 citations · 4 across the 13 of their papers we have counts for
14 papers
Planarity and dimension II
Heather S. Blake, Jędrzej Hodor, Piotr Micek +2
The dimension of a poset is the minimum positive integer such that is an induced subposet of equipped with the product order. We give a constant-factor p…
Navigating Posets with Few Maps
Stefan Felsner, Jędrzej Hodor, Giacomo Ortali +1
We study two new parameters for finite posets motivated by the problem of efficiently determining the set of successors of a given element. A plane map of a poset is a…
Sample compression schemes for balls in structurally sparse graphs
Romain Bourneuf, Jędrzej Hodor, Piotr Micek +1
Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. In a sample compression scheme, we…
Centered colorings and weak coloring numbers in minor-closed graph classes
Jędrzej Hodor, Hoang La, Piotr Micek +1
Let be a proper minor-closed class of graphs. Given the minors excluded in , we determine the maximum -centered chromatic number and the maximum th…
A coarse Gallai theorem
Marc Distel, Ugo Giocanti, Jędrzej Hodor +2
We prove that there exist functions and such that for all positive integers and , for every graph and every subset of the vertices of , either contain…
Local dimension of a Boolean lattice
Jędrzej Hodor, Jakub Sordyl
For every integer with , we prove that the local dimension of a poset consisting of all the subsets of equipped with the inclusion relation is strictl…
Covering graphs by isometric trees
Paul Bastide, Julien Duron, Jędrzej Hodor +2
A connected subgraph of a graph is isometric if it preserves distances. Recently, graphs admitting a vertex or edge covering by a small number of isometric paths have been studied.…
Planarity and dimension I
Heather Smith Blake, Jędrzej Hodor, Piotr Micek +2
The dimension of a partially ordered set (poset for short) is the least positive integer such that is isomorphic to a subposet of with the natural produc…
Cube Height, Cube Width and Related Extremal Problems for Posets
Paul Bastide, Jędrzej Hodor, Hoang La +1
Given a poset , a family of sets indexed by the elements of is called an inclusion representation of if in if and only if…
Centered colorings in minor-closed graph classes
Jędrzej Hodor, Hoang La, Piotr Micek +1
A vertex coloring of a graph is -centered if for every connected subgraph of , either uses more than colors on , or there is a color that appears exact…
Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen +1
A graph contains a graph as an induced minor if can be obtained from after vertex deletions and edge contractions. We show that for every -vertex planar graph $H…
Boolean dimension of a Boolean lattice
Marcin Briański, Jędrzej Hodor, Hoang La +2
For every integer with , we prove that the Boolean dimension of a poset consisting of all the subsets of equipped with the inclusion relation is stric…
The grid-minor theorem revisited
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor +6
We prove that for every planar graph of treedepth , there exists a positive integer such that for every -minor-free graph , there exists a graph of treewidth a…
Reconfiguring Independent Sets on Interval Graphs
Marcin Briański, Stefan Felsner, Jędrzej Hodor +1
We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size are reconfigurable in an -vertex i…