Sparse sets in the complements of graphs with given girth

A. V. Kostochka, D. R. Woodall

Research output: Contribution to journalArticlepeer-review


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 n⊥/3-ε, n⊥/4-ε or n⊥/6-ε whose complement contains no sparse set with more than 8, 7 or 6 edges, respectively.

Original languageEnglish (US)
Pages (from-to)163-174
Number of pages12
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Apr 28 2001
Externally publishedYes


  • Chromatic number
  • Clique covering number
  • Complement of a graph
  • Girth
  • Sparse set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Sparse sets in the complements of graphs with given girth'. Together they form a unique fingerprint.

Cite this