ﻻ يوجد ملخص باللغة العربية
We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.
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
Loebl, Komlos and Sos conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for l
Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwigers conjecture is true for line graphs. We investigate this conjecture on the closely related class of total g
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
In 1972, Tutte posed the $3$-Flow Conjecture: that all $4$-edge-connected graphs have a nowhere zero $3$-flow. This was extended by Jaeger et al.(1992) to allow vertices to have a prescribed, possibly non-zero difference (modulo $3$) between the infl