Maximum $K_r+1$-free graphs which are not $r$-partite

M.Kang; O.Pikhurko

Turán's theorem states that the maximum size of a $K_{r+1}$-free graph $G$ of order $n$ is attained by a complete $r$-partite graph. Here we determine the maximum size of $G$ on the additional restriction that $G$ is not $r$-partite. Also, we present a new proof of the result of Andrásfai, Erdős, and Gallai on the maximum size of an order-$n$ graph whose shortest odd cycle has given length $2l+1$. The extremal graphs are characterized for all feasible values of parameters.

1. Andrásfai B., Erdős P., Sós V. T. On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218.

2. Erdős P. On the graph theorem of Turán, Mat. Lapok 21 (1970), 249–251 (in Hungarian).

3. Erdős P. On a theorem of Rademacher–Turán, Illinois J. Math. 6 (1962), 122–127.

4. Erdős P., Simonovits M. On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334.

5. Häggkvist R. Odd cycles of specified length in nonbipartite graphs, Graph Theory (Cambridge, 1981), Vol. 62 of North-Holland Math. Stud., 89–99, North-Holland, 1982.

6. Turán P. On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436–452 (in Hungarian).

	Maximum $K_r+1$-free graphs which are not $r$-partite
Author	M.Kang, O.Pikhurko kang@informatik.hu-berlin.de, pikhurko@andrew.cmu.edu Institut für Informatik, Humboldt-Universität zu Berlin, D-10099 Berlin, Germany, Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Abstract	Turán's theorem states that the maximum size of a $K_{r+1}$-free graph $G$ of order $n$ is attained by a complete $r$-partite graph. Here we determine the maximum size of $G$ on the additional restriction that $G$ is not $r$-partite. Also, we present a new proof of the result of Andrásfai, Erdős, and Gallai on the maximum size of an order-$n$ graph whose shortest odd cycle has given length $2l+1$. The extremal graphs are characterized for all feasible values of parameters.
Keywords	free graph, complete partite graph, extremal graph
DOI	doi:10.30970/ms.24.1.12-20
Reference	1. Andrásfai B., Erdős P., Sós V. T. On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218. 2. Erdős P. On the graph theorem of Turán, Mat. Lapok 21 (1970), 249–251 (in Hungarian). 3. Erdős P. On a theorem of Rademacher–Turán, Illinois J. Math. 6 (1962), 122–127. 4. Erdős P., Simonovits M. On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334. 5. Häggkvist R. Odd cycles of specified length in nonbipartite graphs, Graph Theory (Cambridge, 1981), Vol. 62 of North-Holland Math. Stud., 89–99, North-Holland, 1982. 6. Turán P. On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), 436–452 (in Hungarian).
Pages	12-20
Volume	24
Issue	1
Year	2005
Journal	Matematychni Studii
Full text of paper	pdf
Table of content of issue	html