Maximum Kr+1 -free graphs which are not r-partite
By Mihyun Kang and Oleg PikhurkoMat. Studii, 24 (2005), 12-20
Abstract
Tur'an's theorem states that the maximum size of an Kr+1 -free graph G of order n is attained by a complete r-partite graph. Here we determine the maximum of e(G) and describe all extremal graphs on the additional restriction that G is not r-colorable. Also, we determine the maximum size of an order-n graph whose shortest odd cycle has given length 2l+1.
Download
- pdf - maxkrfree.pdf
