Sparse sets in the complements of graphs with given girth Original Research Article

A set of edges in a graph is sparse if no two of these edges belong to the same clique. It is shown here that if a graph has girth at least 5, 6 or 8 then the largest number of edges in a sparse set in its complement is at most 8, 7 or 6, respectively; this result is complete and best possible. It follows that if ε>0, then for sufficiently large n there exists a graph with n vertices and chromatic number greater than n1/3−ε, n1/4−ε or n1/6−ε whose complement contains no sparse set with more than 8, 7 or 6 edges, respectively.