Jernej Azarija: The isomorphism problem, strongly-regular graphs and an efficient algorithm for the clique number

Datum objave: 8. 5. 2015
Seminar za diskretno matematiko
Torek, 12. 5. 2015, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. The talk will begin by introducing some basic properties of the isomorphism problem.  This will in turn lead to the motivation for the notion of strongly-regular graphs. After briefly describing the state of affairs of this topic we will show how their classification motivated an efficient algorithm for the clique number of large graphs. Some interesting relationships with eigenvalues of graphs will be mentioned along the way.