The ErdÖs-Jacobson-Lehel conjecture on potentially Pk-graphic sequence is true *
1Department of Mathematics University of Science and Technology of China Hefei 230026 China
A variation in the classical Turán extremal problem is studied. A simple graph G of order n is said to have property Pk if it contains a clique of size k+1 as its subgraph. An n-term nonincreasing nonnegative integer sequence π=(d1,d2,...,dn) is said to be graphic if it is the degree sequence of a simple graph G of order n and such a graph G is referred to as a realization of π . A graphic sequence π is said to be potentially Pk graphic if it has a realization G having property P k . The problem: determine the smallest positive even number σ(k,n) such that every n term graphic sequence π=(d1,d2,...,dn) without zero terms and with degree sum σ(π)=d1+d2+...+dn at least σ(k,n) is potentially Pk graphic has been proved positive.