On the number of K4-saturating edges

József Balogh, Hong Liu

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be a K4-free graph; an edge in its complement is a K4-saturating edge if the addition of this edge to G creates a copy of K4. Erdos and Tuza conjectured that for any n-vertex K4-free graph G with ⌊n2/4⌋+1 edges, one can find at least (1+o(1))n216 K4-saturating edges. We construct a graph with only 2n233 K4-saturating edges. Furthermore, we prove that it is best possible, i.e., one can always find at least (1+o(1))2n233 K4-saturating edges in an n-vertex K4-free graph with ⌊n2/4⌋+1 edges.

Original languageEnglish (US)
Pages (from-to)250-257
Number of pages8
JournalJournal of Combinatorial Theory. Series B
Volume109
DOIs
StatePublished - Nov 1 2014

Keywords

  • Erdos-Tuza conjecture
  • Extremal number
  • Graphs
  • K
  • Saturating edges

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On the number of K4-saturating edges'. Together they form a unique fingerprint.

Cite this