11 papers
Relative Dimension of Posets
Dominik Dürrschnabel, Jędrzej Hodor, Piotr Micek +2
Dimension of partially ordered sets (posets for short) can be seen as a measure of how much space is needed to store posets. Refining the definition of dimension, or actually the l…
Superlinear separation between linear and centered colorings
Jędrzej Hodor, Piotr Micek
A vertex-coloring of a graph is centered if every connected subgraph has a vertex with a unique color. A vertex-coloring of a graph is linear if every path in the graph has a verte…
Product structure of graphs excluding a topological minor
Jędrzej Hodor, Hoang La, Piotr Micek +1
We prove that, for all positive integers and and every graph with , there exists a positive integer such that every graph with $\mat…
Row pathwidth of complete binary trees
Jędrzej Hodor, Piotr Micek
We show that if a complete binary tree of height is isomorphic to a subgraph of the strong product of a graph and a path, then is . This solves a pro…
Optimal tree-decompositions with bags of bounded pathwidth
Kevin Hendrey, Robert Hickingbotham, Jędrzej Hodor +1
We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for…
Treedepth and 2-treedepth in graphs with no long induced paths
Jędrzej Hodor, Freddie Illingworth, Tomasz Mazur
Huynh, Joret, Micek, Seweryn, and Wollan (Combinatorica, 2022) introduced a graph parameter, later referred to as 2-treedepth and denoted . The parameter is t…
Weak coloring numbers of minor-closed graph classes
Jędrzej Hodor, Hoang La, Piotr Micek +1
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed g…
Quickly excluding an apex-forest
Jędrzej Hodor, Hoang La, Piotr Micek +1
We give a short proof that for every apex-forest on at least two vertices, graphs excluding as a minor have layered pathwidth at most . This improves upon a resu…
The depth of Tsirelson's norm
Kevin Beanland, Jędrzej Hodor
Tsirelson's norm on is defined as the supremum over a certain collection of iteratively defined, monotone increasing norms . For each positive…
Forcing the Wheel
Jędrzej Hodor, William T. Trotter
Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order…
Counting Unions of Schreier Sets
Kevin Beanland, Dmitriy Gorovoy, Jȩdrzej Hodor +1
A subset of positive integers is a Schreier set if it is non-empty and (here is the cardinality of ). For each positive integer , we define $k…