ﻻ يوجد ملخص باللغة العربية
What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcal{G}$ as $nto infty$? We answer this question for a variety of sparse graph classes $mathcal{G}$. In particular, we show that the answer is $Theta(n^{alpha_d(T)})$ where $alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$, for some integer $d$ that depends on $mathcal{G}$. For example, when $mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $mathcal{G}$ is the class of graphs containing no $K_{s,t}$-minor ($tgeq s$) then $d=s-1$; and when $mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.
Let $t$ be a positive real number. A graph is called $t$-tough, if the removal of any cutset $S$ leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough, if the t
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). Janos Pach (1981) answered this question in the negative. We strengthen this re
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vertex disjoint paths in the complement of the input graph. More precisely
Given a family $mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $phicolon Ito mathcal{I}$ where for each $vin I$, $v$ is contained in $phi(v)$. Aharoni, Briggs, J. Kim, a
A class of graphs is $chi$-bounded if there exists a function $f:mathbb Nrightarrow mathbb N$ such that for every graph $G$ in the class and an induced subgraph $H$ of $G$, if $H$ has no clique of size $q+1$, then the chromatic number of $H$ is less