Ramsey Numbers for Line Graphs Given a graph, the classical Ramsey number R(k, l) is the least number of vertices that need to be in the graph for the existence of a clique of size k or an independent set of size l. Finding R(k, l) exactly has been a notoriously hard problem. Even R(k, 3) has not been determined for all values of k. Hence finding the Ramsey number for subclasses of graphs is an interesting question. It is known that even for clawfree graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of clawfree graphs. The question with respect to line graph L(G) is equivalent to the minimum number of edges the underlying graph G needs to have for the existence of a vertex with degree k or a matching of size l. Chvatal and Hanson determined this exactly for line graphs of simple graphs. Later Balachandran and Khare gave the same bounds with a different proof. In this paper we find Ramsey numbers for line graph of multi graphs thereby extending the results of Chvatal and Hanson. Here we determine the maximum number of edges that a multigraph can have, when its matching number, multiplicity, and maximum degree are bounded, and characterize such graphs.

A generalization of generalized Paley graphs and new lower bounds for R(3, q) Generalized Paley graphs are cyclic graphs constructed from  quadratic or higher residues of finite fields. Using this type of cyclic graphs to study the lower bounds for classical Ramsey numbers, has high computing efficiency in both looking for parameter sets and computing clique numbers. We have found a new generalization of generalized Paley graphs, i.e. automorphism cyclic graphs, also having the same advantages. In this paper we study the properties of the parameter sets of automorphism cyclic graphs, and develop an algorithm to compute the order of the maximum independent set, based on which we get new lower bounds for 8 classical Ramsey numbers: R(3,22) geq 131, R(3,23) geq 137, R(3,25) geq 154, R(3,28) geq 173, R(3,29) geq 184, R(3,30) geq 190, R(3,31) geq 199, R(3,32) geq 214. Furthermore, we also get R(5,23) geq 521 based on R(3,22) geq 131. These nine results above improve their corresponding best known lower bounds.