 CARMA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
 Speaker: Novi Herawati Bong, The University of Newcastle
 Title: Extremal Graphs with No Triangles and Squares
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 3:00 pm, Thu, 24^{th} Oct 2013
 Abstract:
Extremal graph theory includes problems of determining the maximum number of edges in a graph on $n$ vertices that contains no forbidden subgraphs. We consider only simple graphs with no loops or multiple edges and the forbidden subgraphs under consideration are cycles of length 3 and 4 (triangle and square). This problem was proposed by Erdos in 1975. Let $n$ denote the number of vertices in a graph $G$. By $ex(n; {C3,C4})$, or simply $ex(n;4)$ we mean the maximum number of edges in a graph of order $n$ and girth at least $g \geq 5$. There are only 33 exact values of $ex(n;4)$ currently known. In this talk, I give an overview of the current state of research in this problem, regarding the exact values, as well as the lower bound and the upper bound of the extremal numbers when the exact value is not known.
 [Permanent link]
