𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Packing triangles in a graph and its complement

✍ Scribed by Peter Keevash; Benny Sudakov

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
127 KB
Volume
47
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

How few edge‐disjoint triangles can there be in a graph G on n vertices and in its complement $\overline {G}$? This question was posed by P. ErdΕ‘s, who noticed that if G is a disjoint union of two complete graphs of order n/2 then this number is n^2^/12 + o(n^2^). ErdΕ‘s conjectured that any other graph with n vertices together with its complement should also contain at least that many edge‐disjoint triangles. In this paper, we show how to use a fractional relaxation of the above problem to prove that for every graph G of order n, the total number of edge‐disjoint triangles contained in G and $\overline {G}$ is at least n^2^/13 for all sufficiently large n. This bound improves some earlier results. We discuss a few related questions as well. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 47: 203–216, 2004

πŸ“œ SIMILAR VOLUMES

The minimum number of subgraphs in a gra
The minimum number of subgraphs in a graph and its complement
✍ Lane Clark πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 265 KB πŸ‘ 2 views

## Abstract For a graphb __F__ without isolated vertices, let __M__(__F__; __n__) denote the minimum number of monochromatic copies of __F__ in any 2‐coloring of the edges of __K__~__n__~. Burr and Rosta conjectured that when __F__ has order __t__, size __u__, and __a__ automorphisms. Independent

Every (p, p-2) graph is contained in its
Every (p, p-2) graph is contained in its complement
✍ David Burns; Seymour Schuster πŸ“‚ Article πŸ“… 1977 πŸ› John Wiley and Sons 🌐 English βš– 120 KB πŸ‘ 1 views

## Abstract The following is proved: If __G__ is graph of order __p__ (β‰₯2) and size __p__‐2, then there exists an isomorphic embedding of __G__ into its complement.

On packing 3-vertex paths in a graph
On packing 3-vertex paths in a graph
✍ Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 276 KB πŸ‘ 2 views
A graph and its complement with specifie
A graph and its complement with specified properties. IV. Counting self-complementary blocks
✍ Jin Akiyama; Frank Harary πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 220 KB

## Abstract In this series, we investigate the conditions under which both a graph __G__ and its complement G possess certain specified properties. We now characterize all the graphs __G__ such that both __G__ and G have the same number of endpoints, and find that this number can only be 0 or 1 or

Degree sum for a triangle in a graph
Degree sum for a triangle in a graph
✍ Genghua Fan πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 379 KB πŸ‘ 1 views

Let %(n; e) denote the class of graphs on n vertices and e edges. Define f(n, e) = min max{C:=, d(u,):{u,, up, uJ} induces a triangle in G}, where the maximum is taken over all triangles in the graph G and the minimum is taken over all G in %(n; e). From Turan's theorem, f(n, e) = 0 if e 5 n 2 / 4 ;