Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Tuzas conjecture for triangulations and graphs with small treewidth
97
0
0.0
(
0
)
Added by
F\\'abio Botler
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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, including 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.
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 conjecture 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 studied. 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 who 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$ such 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
