Till innehåll på sidan

Patrick Schweitzer: Competition Numbers, Quasi-Line Graphs and Holes

Patrick Schweitzer, University of Luxembourg

Tid: Ti 2012-04-24 kl 10.15

Plats: Room 3721, Department of Mathematics, KTH, Lindstedtsvägen 25, 7th floor

Exportera till kalender

(Note the room: 3721)

The competition graph of a directed acyclic graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. By adding isolated vertices, every undirected graph can be turned into the competition graph of some directed acyclic graph. The number of vertices that need to be added is called the competition number. I will talk about two techniques to prove upper bounds of competition numbers. These techniques can be used to resolve conjectures by Opsut and by Kim. I will also describe an alternative to characterization of quasi-line graphs by Chudnovsky and Seymour, which we use to resolve Opsut's conjecture. This is joint work with Brendan McKay and Pascal Schweitzer.

Tillhör: Stockholms Matematikcentrum
Senast ändrad: 2012-04-17