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.