A conjecture on triangles of graphs
Copyright policy )A conjecture on triangles of graphs
The author conjectured in 1981: If a grah G does not contain more than k pairwise edge-disjoint triangles, then there exists a set of at most 2k edges that meets all triangles of G. In the paper this conjecture is proved for various classes of graphs (planar graphs, graphs with n vertices and at least \((7/16)n^ 2\) edges, chordal graphs without a complete subgraph on 5 vertices). Related results for 3-uniform hypergraphs and digraphs as well as weaker and stronger versions of the conjecture for special classes of graphs are discussed. Open problems are presented.
- Hungarian Academy of Sciences Hungary
Extremal problems in graph theory, 3-uniform hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), transversal number, Hypergraphs, triangles, chordal graphs, planar graphs, digraphs
Extremal problems in graph theory, 3-uniform hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), transversal number, Hypergraphs, triangles, chordal graphs, planar graphs, digraphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).36 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!