4 papers
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…