TY - JOUR

T1 - Sparse sets in the complements of graphs with given girth

AU - Kostochka, A. V.

AU - Woodall, D. R.

N1 - Funding Information:
∗Corresponding author. E-mail address: sasha@math.nsc.ru (A.V. Kostochka). 1This work was carried out while the Brst author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation f or Fundamental Research.

PY - 2001/4/28

Y1 - 2001/4/28

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Clique covering number

KW - Complement of a graph

KW - Girth

KW - Sparse set

UR - http://www.scopus.com/inward/record.url?scp=0035962195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035962195&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(00)00235-1

DO - 10.1016/S0012-365X(00)00235-1

M3 - Article

AN - SCOPUS:0035962195

VL - 233

SP - 163

EP - 174

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -