اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCaterpillars and alternating paths
128
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$ and $q(m)$ for all $m ge 1$. The two functions $p(n)$ and $q(n)$ can also be interpreted in terms of alternating paths among $n$ disjoint line segments in the plane, whose $2n$ endpoints are in convex position.
قيم البحث
اقرأ أيضاً
We say that a finite set of red and blue points in the plane in general position can be $K_{1,3}$-covered if the set can be partitioned into subsets of size $4$, with $3$ points of one color and $1$ point of the other color, in such a way that, if at
each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set $R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general position, how many points of $Rcup B$ can be $K_{1,3}$-covered? and we prove the following results: (1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$, then there are point sets $Rcup B$, like ${1,3}$-equitable sets (i.e., $r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered. (2) If $r=3g+h$, $b=3h+g$ and the points in $Rcup B$ are in convex position, then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight. (3) There are arbitrarily large point sets $Rcup B$ in general position, with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered. (4) If $ble rle 3b$, then at least $frac{8}{9}(r+b-8)$ points of $Rcup B$ can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P
aths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.
The theme of this article is a reciprocity between bounded up-down paths and bounded alternating sequences. Roughly speaking, this ``reciprocity manifests itself by the fact that the extension of the sequence of numbers of paths of length $n$, consis
ting of diagonal up- and down-steps and being confined to a strip of bounded width, to negative $n$ produces numbers of alternating sequences of integers that are bounded from below and from above. We show that this reciprocity extends to families of non-intersecting bounded up-down paths and certain arrays of alternating sequences which we call alternating tableaux. We provide as well weight
It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglog n)$. This improves the previous bound of $O(log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).
A grounded L-graph is the intersection graph of a collection of L shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omega^4$. This improves
the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $chi$-bounded. We also survey $chi$-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
