Wood~ recently showed that every graph $G$ of pathwidth $h$ and $\Delta(G)\ge1$ admits a $T$-partition of width at most $4(h+1)^2\Delta(G)$ for some tree $T$ with $pw(T)\leq2h+1$. In this paper, we establish an analogous result for tree-depth, which is a stronger parameter than pathwidth. We prove that every connected graph with tree-depth $h$ admits a $T$-partition of width at most $\mathrm{max}\{1, (4h-10)\Delta(G)+1\}$ for some tree $T$ with $\operatorname{rad}(T)\leq h-1$.
Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Ho\`ang, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)...
A family of paths in a graph $G$ strongly separates the edges of $G$ if for every ordered pair of distinct edges $(e,f)$ some path in the family contains $e$ and avoids $f$; the minimum size of such a family is denoted by $\operatorname{ssp}(G)$. Bonamy, Botler, Dross, Naia, and Skokan proved, for every $n$-vertex grap...
Daniel W. Cranston, Jared Noyman, Ge-Xin Yu· 0 citations
We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of...
Wouter Cames van Batenburg, Quentin Claus, G. Joret et al.· 0 citations
We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....
Csongor Beke, V. Boskovic, Nina Kamčev et al.· 0 citations
Let $G$ be a graph. The circumference of $G$, denoted by $cir(G)$, is the length of a longest cycle in $G$, or zero if $G$ is acyclic. In 1993, Broersma, van den Heuvel, Jung, and Veldman conjectured that, for every $t>0$, there is a constant $A=A(t)>0$ such that every 2-connected $t$-tough graph of order $n$ has circu...
Motivated by Mader's conjecture on connectivity keeping trees, we study trees obtained from paths by adding one pendant vertex, as well as related problems in triangle-free graphs. For an integer $m$ and $1\leq i\leq m-1$, let $P_m^+(i)$ denote the tree obtained from a path of order $m-1$ by adding one pendant vertex a...
Meng-Han Ma, Qing-Hai Liu, Li-Ping Zhang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
