Please use this identifier to cite or link to this item: https://idr.nitk.ac.in/jspui/handle/123456789/8897
Title: Ramsey Numbers for Line Graphs
Authors: Abbasi, H.
Basavaraju, M.
Gurushankar, E.
Jivani, Y.
Srikanth, D.
Issue Date: 2020
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
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.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/8897
Appears in Collections:2. Conference Papers

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.