Premium
Packing triangles in a graph and its complement
Author(s) -
Keevash Peter,
Sudakov Benny
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20031
Subject(s) - combinatorics , mathematics , disjoint sets , complement (music) , graph , discrete mathematics , biochemistry , chemistry , complementation , gene , phenotype
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