Name
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. Erdős 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.jctb.2014.06.008 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Graphs,K4,Saturating edges,Extremal number,Erdős–Tuza conjecture | Journal | 109 |
Issue | ISSN | Citations |
C | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 4 | 2 |