Please use this identifier to cite or link to this item: https://idr.l4.nitk.ac.in/jspui/handle/123456789/8897
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAbbasi, H.
dc.contributor.authorBasavaraju, M.
dc.contributor.authorGurushankar, E.
dc.contributor.authorJivani, Y.
dc.contributor.authorSrikanth, D.
dc.date.accessioned2020-03-30T10:22:58Z-
dc.date.available2020-03-30T10:22:58Z-
dc.date.issued2020
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, Vol.12016 LNCS, , pp.197-208en_US
dc.identifier.urihttp://idr.nitk.ac.in/jspui/handle/123456789/8897-
dc.description.abstractGiven 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.en_US
dc.titleRamsey Numbers for Line Graphsen_US
dc.typeBook chapteren_US
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.