✦ LIBER ✦

Graphic sequences that have a realization with large clique number

✍ Scribed by Mubayi, Dhruv

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 119 KB
Volume: 34
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(200005)34:1<20::aid-jgt3>3.0.co;2-v

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that for k ≥ 5, every (2k + 2)-element graphic sequence of positive terms with sum at least 4k(k -1) can be realized by a graph containing K k+1 . Also, this bound is sharp. Furthermore, for 2k + 3 ≤ n ≤ k(5k -11)/(2k -4), we construct a graphic n-element positive sequence with sum (2k -4)(2k -1) + 2(n -1) that has no realization containing K k+1 . This construction partially answers a question of Erdős et al. in the negative.