F-free interval graphs

Abstract

Kruskal's 'greedy tree algorithm' plays an important part in both the theory and application of chordal graphs. A similar 'greedy path algorithm' is shown to play a corresponding role for 'F-free interval graphs,' a class that contains the much-studied families of indifference graphs and P₄, C₄-free graphs. These latter graphs can also be viewed as the coincidence of the basic notions of intersection graphs and containment graphs, with the greedy path algorithm playing a special role for them and for the even more selective class of threshold graphs.