Sparse sets in the complements of graphs with given girth (Q5936026)

A set of edges of a graph \(G\), no two of which belong to the same clique is said to be sparse. The cardinality of a largest sparse set of \(G\) is denoted by \(h(G)\). It was conjectured that \(h(G)\leq \chi (\overline{G})\), where \(\chi \) is the chromatic number and \(\overline{G}\) is the complement of \(G\). This was proved to be false for almost all graphs by Erdős. He showed that for sufficiently large \(h\) there is a positive constant \(c_h\) such that for sufficiently large \(n\) there is an \(n\)-vertex graph \(G\) with no isolated vertices for which \(h(G)\leq h\) and \(\chi (\overline{G})\geq n^{c_h}\). NEWLINENEWLINENEWLINEIn this paper the authors prove that if the girth \(g(G)\) of a graph \(G\) is at least 5, 6 or 8 (respectively), then \(h(\overline{G})\leq 8,7\) or 6 (accordingly). This leads to the corollary that for every \(\varepsilon > 0\), we can take \(c_8>\frac{1}{3}-\varepsilon\), \(c_7 > \frac{1}{4}-\varepsilon\), and \(c_6 > \frac{1}{6}-\varepsilon\). NEWLINENEWLINENEWLINEThe proof technique is a detailed case by case discussion and involves a lemma linking the girth of a graph to the minimum number of edges required to realize it.