The Erdős-Jacobson-Lehel conjecture on potentially \(P_k\)-graphic sequence is true (Q1128134): Difference between revisions

Initially \(\text{NS}_n\) denotes the set of all integer sequences \(\pi=(d_1,d_2,\dots,d_n)\) such that \(n-1\geq d_1\geq d_2\geq\dots \geq d_n\geq 0\); \(\sigma(\pi)=\sum_1^nd_i\). For a property \(Q\), \(\pi\) is graphic (respectively potentially \(Q\)-graphic) if there exists a simple graph \(G\) with degree sequence \(\pi\) (respectively with degree sequence \(\pi\) and possessing property \(Q\)). A graph has property \(P_k\) iff it contains a subgraph of structure \(K_{k+1}\). \textit{P. Erdős, M. S. Jacobson}, and \textit{J. Lehel} [Graphs realizing the same degree sequences and their respective clique numbers, in Alavi, Yousef (ed.) et al., Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988. New York: John Wiley \&{} Sons Ltd. Wiley-Interscience Publication. 439-449 (1991; Zbl 0840.05093)] and \textit{R. J. Gould, M. S. Jacobson}, and \textit{J. Lehel} [Potentially \(G\)-graphical degree sequences, described as ``to appear''] have sought the smallest positive even integer \(\sigma(k,n)\) such that every \(\pi\) without zero terms and with \(\sigma(\pi)\geq \sigma(k,n)\) is potentially \(P_k\)-graphic, and have conjectured that \(\sigma(k,n)=(k-1)(2n-k)+2\) for \(n\) sufficiently large; for \(k=1,2,3\) the conjecture has been proved by various authors for \(n\geq 6,8,10\) respectively; the first two of the present authors have proved that \(\sigma(k,2k+1)=4k^2-2k\) [An extremal problem on the potentially \(P_k\)-graphical sequence, in International Symposium on Combinatorics and Applications, June 28-30, 1996, Tianjin (editors Chen, W. Y. C. et al.), Nankai University, Tianjin, 266-276 (1996)]. The reviewer has not checked the validity of the proofs, which rely in part on an unpublished theorem. The main result is that the conjectured value of \(\sigma(k,n)\) is correct for \(n\geq{k\choose 2}+3\), \(k\geq 5\).