Extremal graphs for connectedness

Graphs, Hypergraphs, and Computing

22 April 14:00 - 15:30

Penny Haxell - University of Waterloo

It is known that the topological connectedness of the independence complex of the line graph of G is bounded below by the matching number of G (minus 2). This parameter turns out to be important for some old conjectures about hypergraphs, in particular Ryser's conjecture on r-partite r-uniform hypergraphs. We study the bipartite graphs G that are extremal for this parameter, and as one consequence characterise the 3-partite 3-uniform hypergraphs that are extremal for Ryser's conjecture.

Joint work with Lothar Narins and Tibor Szabo
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to