We investigate whether K,-free graphs with few repetitions in the degree sequence may have independence number o(n). We settle the cases r = 3 and r >/5, and give partial results for the very interesting case r=4.
In an earlier article I-4] it is shown that triangle-free graphs in which no term of the degree sequence occurs more than twice must be bipartite, but that there exist triangle-free graphs with arbitrarily large chromatic number in which no degree occurs more than three times. It is easy to see that the large chromatic number in such graphs is not due to small independence number, since the neighbors of a vertex are independent, and the restriction on repeated degrees forces there to be vertices of large degree. If one excludes K 4 rather than K3, the situation is considerably more mysterious,
For a graph G we define f(G) to be the maximum number of occurrences of an element of the degree sequence of G. That is, iff(G)=k, then some set of k vertices have the same degree but no set of k + 1 vertices have the same degree. Note that f(G) >~ 2 if G has at least two vertices. Throughout the paper we will assume that our graphs have no isolated vertices so that 6 ~> 1. The number of vertices of G will be denoted by n or v(G). The number of edges of G will be denoted by e(G). We shall use /3 to denote the independence number of a graph. We address the following question in this paper.