Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTree densities in sparse graph classes
91
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. In this paper we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the class of chordal graphs, split graphs, claw-free graphs and $2K_2$-free graphs.
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 result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) a subdivision of the complete graph $K_t$ with multiplicity $t$, for every finite $t$. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite $n$-vertex subgraph has a balanced separator of size $O(sqrt{n})$. The graph is $mathcal{T}_6boxtimes P_{!infty}$, where $mathcal{T}_k$ is the universal treewidth-$k$ countable graph (which we define explicitly), $P_{!infty}$ is the 1-way infinite path, and $boxtimes$ denotes the strong product. More generally, for every positive integer $t$ we construct a countable graph that contains every countable $K_t$-minor-free graph and has the above key properties. Our final contribution is a construction of a countable graph that contains every countable $K_t$-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) above is best possible).
153 -
Pavel Dvov{r}ak
, Duv{s}an Knop (Department ofn Applied Mathematics Charles University Prague
2016
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, we show that if a graph has tree-width at most w and its complement is closed under Bondy-Chvatal closure, then it is possible to bound neighborhood diversity of the complement by a function of w only. A simpler proof where tree-depth is used instead of tree-width is also presented.
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, and M. Kim [Rainbow independent sets in certain classes of graphs. arXiv:1909.13143] determined for various graph classes $mathcal{C}$ whether $mathcal{C}$ satisfies a property that for every $n$, there exists $N=N(mathcal{C},n)$ such that every family of $N$ independent sets of size $n$ in a graph in $mathcal{C}$ contains a rainbow independent set of size $n$. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of $r$-powers of graphs in a bounded expansion class.
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 than or equal to $f(q)$. We denote by $W_n$ the wheel graph on $n+1$ vertices. We show that the class of graphs having no vertex-minor isomorphic to $W_n$ is $chi$-bounded. This generalizes several previous results; $chi$-boundedness for circle graphs, for graphs having no $W_5$ vertex-minors, and for graphs having no fan vertex-minors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
