Zobrazeno 1 - 10
of 297
pro vyhledávání: '"Micek, Piotr"'
A vertex coloring $\varphi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$, either $\varphi$ uses more than $p$ colors on $H$, or there is a color that appears exactly once on $H$. We prove that for every fixed positive int
Externí odkaz:
http://arxiv.org/abs/2411.02122
We show that every $n$-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O(\sqrt{n}\log^2 n)$. Equivalently, every $n$-vertex planar graph $G$ has a set $X$ of $O(\sqrt{n}\log^2
Externí odkaz:
http://arxiv.org/abs/2407.05936
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 graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free gr
Externí odkaz:
http://arxiv.org/abs/2407.04588
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmovi\'c, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our
Externí odkaz:
http://arxiv.org/abs/2404.17306
An $\ell$-vertex-ranking of a graph $G$ is a colouring of the vertices of $G$ with integer colours so that in any connected subgraph $H$ of $G$ with diameter at most $\ell$, there is a vertex in $H$ whose colour is larger than that of every other ver
Externí odkaz:
http://arxiv.org/abs/2404.16340
Let $T$ be a tree on $t$ vertices. We prove that for every positive integer $k$ and every graph $G$, either $G$ contains $k$ pairwise vertex-disjoint subgraphs each having a $T$ minor, or there exists a set $X$ of at most $t(k-1)$ vertices of $G$ suc
Externí odkaz:
http://arxiv.org/abs/2403.06370
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension $k$ as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth
Externí odkaz:
http://arxiv.org/abs/2308.11950
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
Externí odkaz:
http://arxiv.org/abs/2307.16671
Autor:
Dujmović, Vida, Hickingbotham, Robert, Hodor, Jędrzej, Joret, Gweanël, La, Hoang, Micek, Piotr, Morin, Pat, Rambaud, Clément, Wood, David R.
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes
Externí odkaz:
http://arxiv.org/abs/2307.02816
Autor:
Dujmović, Vida, Hickingbotham, Robert, Joret, Gwenaël, Micek, Piotr, Morin, Pat, Wood, David R.
Publikováno v:
Combinatorics, Probability and Computing (2024), 33, pp. 85--90
We prove that for every tree $T$ of radius $h$, there is an integer $c$ such that every $T$-minor-free graph is contained in $H\boxtimes K_c$ for some graph $H$ with pathwidth at most $2h-1$. This is a qualitative strengthening of the Excluded Tree M
Externí odkaz:
http://arxiv.org/abs/2303.14970