Ramsey Numbers for Line Graphs
No Thumbnail Available
Date
2020
Authors
Abbasi, H.
Basavaraju, M.
Gurushankar, E.
Jivani, Y.
Srikanth, D.
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, Vol.12016 LNCS, , pp.197-208