Ramsey Numbers for Line Graphs

Abstract

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 claw-free graphs, finding Ramsey number is as hard as for general graphs for infinite number of cases. Line graphs are an important subclass of claw-free 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. Chv�tal 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 Chv�tal 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. � 2020, Springer Nature Switzerland AG.