ترغب بنشر مسار تعليمي؟ اضغط هنا

On Tuzas conjecture for triangulations and graphs with small treewidth

97   0   0.0 ( 0 )
 نشر من قبل F\\'abio Botler
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Tuza (1981) conjectured that the size $tau(G)$ of a minimum set of edges that intersects every triangle of a graph $G$ is at most twice the size $ u(G)$ of a maximum set of edge-disjoint triangles of $G$. In this paper we present three results regarding Tuzas Conjecture. We verify it for graphs with treewidth at most $6$; we show that $tau(G)leq frac{3}{2}, u(G)$ for every planar triangulation $G$ different from $K_4$; and that $tau(G)leqfrac{9}{5}, u(G) + frac{1}{5}$ if $G$ is a maximal graph with treewidth 3. Our first result strengthens a result of Tuza, implying that $tau(G) leq 2, u(G)$ for every $K_8$-free chordal graph $G$.



قيم البحث

اقرأ أيضاً

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, inclu ding planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
112 - Jacob D. Baron , Jeff Kahn 2014
An old conjecture of Zs. Tuza says that for any graph $G$, the ratio of the minimum size, $tau_3(G)$, of a set of edges meeting all triangles to the maximum size, $ u_3(G)$, of an edge-disjoint triangle packing is at most 2. Here, disproving a conjec ture of R. Yuster, we show that for any fixed, positive $alpha$ there are arbitrarily large graphs $G$ of positive density satisfying $tau_3(G)>(1-o(1))|G|/2$ and $ u_3(G)<(1+alpha)|G|/4$.
We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been s tudied. We show that $$ left(c cdot frac{kcdot 2^k cdot n}{log k} right)^n cdot 2^{-frac{k(k+3)}{2}} cdot k^{-2k-2} leq T_{n,k} leq left(k cdot 2^k cdot nright)^n cdot 2^{-frac{k(k+1)}{2}} cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.
A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib wh o proposed a hypergraph version of this conjecture, and also studied its implied fraction
A $k$-linear coloring of a graph $G$ is an edge coloring of $G$ with $k$ colors so that each color class forms a linear forest -- a forest whose each connected component is a path. The linear arboricity $chi_l(G)$ of $G$ is the minimum integer $k$ su ch that there exists a $k$-linear coloring of $G$. Akiyama, Exoo and Harary conjectured in 1980 that for every graph $G$, $chi_l(G)leq left lceil frac{Delta(G)+1}{2}rightrceil$ where $Delta(G)$ is the maximum degree of $G$. First, we prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture in some classes of graphs like cubic graphs and triangle-free planar graphs for which the conjecture was already known to be true. Next, for every 2-degenerate graph $G$, we show that $chi_l(G)=leftlceilfrac{Delta(G)}{2}rightrceil$ if $Delta(G)geq 5$. We conjecture that this equality holds also when $Delta(G)in{3,4}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs. All our proofs can be converted into linear time algorithms.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا