CAESAREA ROTHSCHILD INSTITUTE
at the
University of Haifa
 
SPECIAL COMBINATORIAL ALGORITHMS COLLOQUIUM
Monday 31 Oct 14:15
 

On the maximum difference between several graph invariants.

 

Alain Hertz

 

École Polytechnique de Montréal & GERAD

 

A graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. Although bounds on invariants have been studied for a long time by graph theorists, the past few years have seen a surge of interest in the systematic study of linear relations (or other kinds of relations) between graph invariants. We focus our attention on the difference between the maximum orders of an induced (linear) forest, an induced tree, an induced bipartite graph, and a stable set. We give upper bounds on these differences, and prove that there are tight.