Search Results

Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which cov …

G. Chartrand, H.V. Kronk, C.E. Wall showed in "The point-arboricity of a graph" (Israel J. Math., 6 (1968), pp. 169–175) that the vertex-set of any planar graph can be partitioned into three induced f …

The following separation property of trees is well-known and in fact easy to prove (see e.g. the paper "Covering a hypergraph of subgraphs" by Noga Alon, Lemma 2.2) Let $T$ be a tree and $r, m$ no …

I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ex …

Let $G$ be a graph s.t. any two cycles $C_1, C_2 \subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph …

I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple. …

The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ su …

I think I have a proof that such a labelling cannot exist if $n$ is even. Suppose we have a labelling $\ell : V(K_m) \to \{ a, b \}$ and a decomposition of $K_{m}$ into a family $\mathcal{P}$ of Hami …

Everybody sits down. The host initiates the exchange of gifts. He stands up and chooses one of the $(n-1)$ others to give his gift to. The person that received the gift stands up and gives his gift to …

Question: For which graphs $H$ is the following true? Every graph that contains $H$ as an induced minor also contains $H$ as an induced topological minor. Definitions: Let $G$ and $H$ be graphs. $H$ …

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in …

A graph drawn in the plane (with edges represented by curves that do not pass through vertices except for their endpoints) is called $k$-quasi-planar if there are is no set of $k$ pairwise intersectin …

I tried to prove the statement for a while and I think I managed to narrow it down to one particularly difficult case. In the end, it led me to a counter example, showing there are no such values $g$ …

Minimizing the number of batches is a typical NP-complete problem. I've seen it under the name 'Load Balancing', but a google-search did not give many results (although the German Wikipedia knows it). …

I mentioned your type of decomposition to my colleague Konstantinos and he pointed out that it had appeared in the literature under the name "strong tree-decomposition"! D. Seese introduced it in 1985 …