ﻻ يوجد ملخص باللغة العربية
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
It is proved that if a graph is regular of even degree and contains a Hamilton cycle, or regular of odd degree and contains a Hamiltonian $3$-factor, then its line graph is Hamilton decomposable. This result partially extends Kotzigs result that a $3
By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposit
A recent result of Condon, Kim, K{u}hn and Osthus implies that for any $rgeq (frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we p
A graph $G$ is said to be ubiquitous, if every graph $Gamma$ that contains arbitrarily many disjoint $G$-minors automatically contains infinitely many disjoint $G$-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite g
A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$